백준 14567 : 선수과목 (Prerequisite)

https://www.acmicpc.net/problem/14567

14567번: 선수과목 (Prerequisite)

 

아무 짝에도 쓸모 없는 공학인증을 받기 위해 노력하는 민욱이를 위하여 전공 과목 수강 순서를 정해주어야 하는 문제다.

위상정렬로 간단하게 해결할 수 있다.

 

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

using namespace std;

int n;
vector<int> edge[1001];
int pre_cnt[1001];
int visited[1001];

void bfs() {
	int cur, next;
	queue<int> q;

	//선수과목이 없는 정점 큐에 삽입
	for (int i = 1; i <= n; i++) {
		if (!pre_cnt[i]) {
			q.push(i);
			visited[i] = 1;
		}
	}

	while (!q.empty()) {
		cur = q.front();
		q.pop();

		for (int i = 0; i < edge[cur].size(); i++) {
			next = edge[cur][i];
			//bfs는 최단거리 알고리즘이므로 거리가 더 짧은 경우가 더 먼저 도착함
			//따라서 선수과목을 모두 듣고 마지막에 방문할 때가 가장 큰 값이므로 max체크는 불필요
			visited[next] = visited[cur] + 1;
			//현재 정점의 선수과목의 수를 하나 줄임
			--pre_cnt[next];
			//선수과목이 더이상 없다면 큐에 삽입
			if (!pre_cnt[next]) q.push(next);
		}
	}
}

void solution() {
	int m;
	int p, c;

	cin >> n >> m;
	while (m--) {
		cin >> p >> c;
		edge[p].push_back(c);
		++pre_cnt[c];
	}

	bfs();

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 4960 kb

시간: 100 ms