[백준]키 순서(2458)

문제 링크 : [백준]키 순서(2458)

2458번: 키 순서

문제 설명

N명의 학생이 존재하고, N명의 학생들의 키 관계가 주어집니다.(Ex : A학생이 B학생보다 크다)

이 때, 정확하게 몇번째로 큰지 알 수 있는 학생의 수를 구하세요.

입력

N(학생의 수, 2 <= N <= 500)

M(관계의 수, 0 <= M <= N(N-1)/2)

A B(A학생이 B학생보다 작다.)

6 6
1 5
3 4
5 4
4 2
4 6
5 2

 

출력

1

 

카테고리

#DFS

 

시간 복잡도 상한

O(N³)

 

해결 방법

1. 자신의 키순서를 정확하게 알기 위해서는 나를 제외한 모든 사람이 자신보다 크거나 작은지를 알아야 합니다.
2. 1을 만족 하려면, (자신보다 큰사람의 수) + (자신보다 작은 사람의 수) = N - 1을 만족하는 사람이 자신의 키 순서를 알 수 있는 사람입니다.
3. A가 B보다 작고, B가 C보다 작다면, A가 C보다 작음을 알 수 있습니다.
4. 즉, 주어진 관계를 통하여 DFS를 이용해서 탐색할 수 있는 노드는 자신보다 작은 사람임을 알 수 있습니다.
5. 문제는 자신보다 큰 사람도 구하여야 합니다.
6. 입력에서 받은 관계는 자신보다 A가 B보다 작은 것이었습니다.
7. 반대로 생각하면 B는 A보다 큽니다.
8. 입력받은 관계를 반대로하는 그래프를 만들어 탐색을 한다면, 자기보다 큰 사람의 수를 구할 수 있습니다.
9. 위 두 그래프를 이용하여 탐색할 수 있는 노드의 수가 N - 1과 같다면 자신의 정확한 키 순서를 알 수 있는 사람입니다.
10. 이렇게 구한 수를 출력합니다.

시간복잡도

O(N)

코드

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int p[501],n,m,a,b,i,j,c;
vector<int> v[2][501];
queue<int> q;
int main(){
	scanf("%d %d",&n,&m);
	while(m--){
		scanf("%d %d",&a,&b);
		v[0][a].push_back(b);
		v[1][b].push_back(a);
	}
	for(j=1;j<=n;j++){
		a=1;
		for(i=0;i<2;i++){
			q.push(j);
			p[i]=i;
			while(!q.empty()){
				b=q.front();q.pop();
				for(m=0;m<v[i][b].size();m++){
					if(p[v[i][b][m]]<j){
						p[v[i][b][m]]=j;
						a++;
						q.push(v[i][b][m]);
					}
				}
			}
		}
		if(a==n)c++;
	}
	printf("%d",c);
}