백준 14567번 선수과목 / 위상정렬

위상정렬 알고리즘 공부 후 처음으로 풀어본 관련문제이다.

비순환 단방향 그래프라는 구조답게 과목들을 수강할때 선수과목이 있는 경우의 모습과 같다.

 

다만 이 문제에서 차이점은 단지 노드들의 순서를 출력하는 것이 아니라 

인접노드 0인 노드들은 1로, 인접노드 0에서 이어진 노드들은 2로, 또 이 노드들에서 이어진 노드들은 3으로 결론내는점 정도가 차이점이다.

 

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL);

	int N, M;
	cin >> N >> M;

	vector<vector<int>> graph(N + 1); // 노드를 1번부터 쓰므로 N + 1
	vector<int> inDgree(N + 1, 0);
	vector<int> answer(N + 1);

	int u, v;
	for (int i = 0; i < M; i++) {
		cin >> u >> v;
		graph[u].push_back(v);
		inDgree[v]++;
	}

	queue<int> q;
	for (int i = 1; i <= N; i++) {
		if (inDgree[i] == 0) {
			q.push(i);
			answer[i] = 1; // 진입차수 시작부터 0인 노드들은 1학기에 듣는다.
		}
	}

	for (int i = 0; i < N; i++) { // 1번부터 N번노드까지 N회반복
        // 사이클 유무 판단 안해도 되는 문제
		int node = q.front();
		q.pop();
		
		for (int adj : graph[node]) {
			inDgree[adj]--;
			if (inDgree[adj] == 0) {
				q.push(adj);
				answer[adj] = answer[node] + 1; // 이부분이 차이점
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		cout << answer[i] << ' ';
	}

	return 0;
}