백준 14567: 선수과목 (Prerequisite)

문제 요약

어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다. 계산을 편리하게 하기 위해 아래와 같이 조건을 간소화하여 계산하기로 하였다.

• 한 학기에 들을 수 있는 과목 수에는 제한이 없다.
• 모든 과목은 매 학기 항상 개설된다.
  
  모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 계산하는 프로그램을 작성하여라.

문제 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 위상 정렬

문제 풀이

위상 정렬과 dp로 풀면 된다. v[idx]는 idx번 과목의 선수과목들을 vector로 넣은 것이다. v[idx]가 비었다면, 첫 학기에 이수할 수 있다는 뜻이다. idx번째 과목의 최소 이수 학기는, v[idx]의 각 원소의 최소 이수학기의 최댓값 + 1이 될 것이다. 이 형태로 dp를 구축해서 탐색하면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, m, dp[1000];
vector<int> v[1000];

int sol(int idx)
{
	if (v[idx].empty()) return 1;
	if (dp[idx]) return dp[idx];
	int temp = 0;
	for (int i = 0; i < v[idx].size(); i++)
		temp = max(temp, sol(v[idx][i]));
	dp[idx] = temp + 1;
	return dp[idx];
}

int main()
{
	int in1, in2;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &in1, &in2);
		v[in2 - 1].push_back(in1 - 1);
	}
	for (int i = 0; i < n; i++)
		printf("%d ", sol(i));
}