[백준] 2458번 키 순서

www.acmicpc.net/problem/2458

2458번: 키 순서

DFS(깊이 우선 탐색)로 풀었다.

일단 정점이 N개인 방향그래프를 만들어준다.

a, b를 입력받으면 a에서 b로 가는 간선을 추가해준다.

그럼 위와 같은 그래프가 만들어질 것이다.

위의 그래프에서 4번 학생만 자신의 키가 몇 번째로 큰지 알 수 있다.

그 이유는 정점 1, 3, 5는 4에 도달할 수 있고 정점 2, 6은 4에서 도달할 수 있는 정점들이기 때문이다.

도달할 수 있는지 없는지는 DFS를 통해 알 수 있다.

그렇게 DFS를 통해 알아낸 도달할 수 있는지 여부는 approach를 완성한다.

i행 j열은 i에서 j로 갈 수 있는지 여부이다.

4행과 4열에서 true의 개수가 6개이다. 그러므로 4번 학생은 몇 번째로 키가 큰지 알 수 있다.

4행에서 쭉 세고 4열에서 쭉 세면 4행 4열은 중복으로 세어지므로 true인 것의 개수는 7이다.

세어줄 때는 i행 i열은 중복으로 세어지므로 i행에서 true의 개수를 쭉 세고 i열에서 true의 개수를 세었을 때

N + 1개이면 i번 학생은 몇 번째로 키가 큰지 알 수 있는 것이다.

#include <iostream>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	int a, b;
	vector<int> graph[501];
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
	}
	vector<bool> visited(n + 1, false);
	vector<vector<bool>> approach(n + 1, vector<bool>(n + 1, false));
	for (int i = 1; i <= n; i++) {
		visited = vector<bool>(n + 1, false);
		stack<int> stack;
		stack.push(i);
		while (!stack.empty()) {
			int cur = stack.top();
			stack.pop();
			if (!visited[cur]) {
				visited[cur] = true;
				approach[i][cur] = true;
				for (int j = 0; j < graph[cur].size(); j++) {
					stack.push(graph[cur][j]);
				}
			}
		}
	}
	int answer = 0;
	for (int i = 1; i <= n; i++) {
		int cnt = 0;
		for (int j = 1; j <= n; j++) {
			if (approach[i][j])
				cnt++;
			if (approach[j][i])
				cnt++;
		}
		if (cnt == n + 1) {
			answer++;
		}
	}
	cout << answer;
	return 0;
}