BOJ14567/ C++

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

14567번: 선수과목 (Prerequisite)

백준 온라인저지 14567번 문제입니다. 

위상정렬을 이용해서 풀었습니다.

#include<iostream>
#include<queue>
#include<vector>
#define MAX 1001
using namespace std;

int N, M;
int PrerequisiteCnt[MAX];
int Prerequisite[MAX];
vector<int> v[MAX];

int max(int a, int b) { return a > b ? a : b; }

void Input() {
	int a, b;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		Prerequisite[b]++;
	}
}

void solution() {
	queue<int> q;
	for (int i = 1; i <= N; i++) {
		if (Prerequisite[i] == 0) {
			q.push(i);
			PrerequisiteCnt[i]++;
		}
	}
		

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

		for (int next = 0; next < v[current].size(); next++) {
			if (--Prerequisite[v[current][next]] == 0) 
				q.push(v[current][next]);
			PrerequisiteCnt[v[current][next]] = max(PrerequisiteCnt[v[current][next]], PrerequisiteCnt[current] + 1);
		}
	}

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

int main(void) {
	Input();
	solution();
}

아이디어

과목을 듣는데 필요한 과목 나열이 아닌 선수 조건이 있을 수 있는 과목들을 듣는데 걸리는 최소시간을 출력하는 문제임

위상정렬을 하며 현재 과목을 이수하는데 걸리는 시간과 선수과목 + 1을 하여 시간이 오래걸리는게 해당 과목을 이수하기 위한 최소 시간임