[백준]2458 키순서

1. 문제

키를 비교하는 몇가지의 조건들이 주어졌을 때, 키 순서를 정확히 알수있는 학생이 몇명되는가?

​

2. 해결

1~N학생이 있을 때 각 학생별로

1. 키가 작은쪽으로 탐색(bfs or dfs)한번,

2. 키가 큰쪽으로 탐색한번을 해서

1 + 2 = N-1이 되는지 확인하고, 되면 그 학생은 정확한 순위를 알 수 있다고 판단.

​

3. 소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

vector<int> to[501];
vector<int> reversedTo[501];


int main() {
	int ans = 0;
	int N, M;
	cin >> N >> M;

	int a, b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		to[a].push_back(b);
		reversedTo[b].push_back(a);
	}

	// 각 학생별로 bfs돈다
	for (int i = 1; i <= N; i++) {
		int cheakedL[501] = { 0, };
		int temp;
		queue<int> q;

		//앞으로 탐색
		int taller = 0;
		q.push(i);
		cheakedL[i] = 1;
		while (!q.empty()) {
			temp = q.front(); q.pop();
			for (int j = 0; j < to[temp].size(); j++) {
				if (cheakedL[to[temp][j]] != 1) {
					q.push(to[temp][j]);
					cheakedL[to[temp][j]] = 1;
					taller += 1;
				}
			}
		}

		//뒤로 탐색
		int shorter = 0;
		q.push(i);
		while (!q.empty()){
			temp = q.front(); q.pop();
			for (int j = 0; j < reversedTo[temp].size(); j++) {
				if (cheakedL[reversedTo[temp][j]] != 1) {
					q.push(reversedTo[temp][j]);
					cheakedL[reversedTo[temp][j]]=1;
					shorter += 1;
				}
			}
 		}
		if (taller + shorter == N - 1) {
			ans += 1;
		}
	}
	cout << ans;

	return 0;
}