[BOJ] 14567번 선수과목 (Prerequisite) (C++)

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

14567번: 선수과목 (Prerequisite)

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, m, indegree[1001];
vector<int> a[1001];

void topologySort(){
	int result[1001];
	queue<int> q;
	
	for(int i = 1; i <= n; i++){
		if(indegree[i] == 0){
			q.push(i);
		}
		result[i] = 1;
	}
	
	while(!q.empty()){
		int cur = q.front();
		q.pop();
		
		for(int i = 0; i < a[cur].size(); i++){
			int next = a[cur][i];
			if(--indegree[next] == 0) {
				q.push(next);
				result[next] = max(result[next], result[cur] + 1);  //★
			}
		}
	}
	
	for(int i = 1; i <= n; i++) 
		cout << result[i] << " ";
}

int main() {
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int x, y;
		cin >> x >> y;
		a[x].push_back(y);
		indegree[y]++;
	}
	topologySort();
	return 0;
}

 

 

1학기부터 시작하므로 result 배열을 1로 초기화한다.

2, 3과목의 경우 1과목 이후 수강하여야 하므로 2학기에 수강할 수 있다.

5과목의 경우 4과목 이후 수강하는 조건이라면 2가 되지만 2과목 이후 수강이라는 조건도 있으므로 3학기에 수강할 수 있다.

 

선수 수강 과목의 학기 + 1 중에 큰 값을 고르는 것이 이 문제의 핵심!!