백준 1005(ACM Craft)

www.acmicpc.net/problem/1005

1005번: ACM Craft

위상정렬 문제이다. 

위상정렬은 연결된 그 전 행위에 대해서 모두 마쳤을때 그 노드로 이동할 수 있는 그래프에 대한 순서이다. 

위상정렬 알고리즘으로는 순서도 알 수 있고, 그 노드까지 실행하는데 필요한 최소값 최댓값 이런 것을 알 수 있다.

 

이 문제는 어떤 행위를 하는데 걸리는 최솟값에 대한 문제이다. 

 

그래프 구성을 한 뒤에 진입차수 위상정렬 알고리즘을 이용해서 최솟값을 결정하도록 하자

 

그래프 구성은 단순히 한 방향으로 구성해도 괜찮다. 코드의 진행도 단방향으로 진행되기 때문이다.

 

진입차수 위상정렬은 다음과 같은 반복으로 구성된다.

 

1. 진입차수가 0인 노드를 queue에 넣기

2. queue에서 차례대로 꺼내면서 연결된 노드의 진입차수를 하나 빼기 

3. 1로 가기 

 

이렇게 반복되는데 이 떄 문제의 조건에 따라서 위상정렬이 어떻게 되는지 배열을 생성해도 되고, 최솟값을 dp에 저장하면서 관찰해도 좋다.

 

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

int N, K;
int indegree[MAX];
int time[MAX];
int dp[MAX];

void init() {
	for (int i = 1; i <= N; i++) {
		indegree[i] = 0;
		time[i] = 0;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		init();
		cin >> N >> K;
		vector<int> graph[MAX];
		queue<int> q;
		for (int i = 1; i <= N; i++) {
			cin >> time[i];
		}
		for (int i = 0; i < K; i++) {
			int a, b;
			cin >> a >> b;
			graph[a].push_back(b);
			indegree[b]++;
		}
		int des;
		cin >> des;
		for (int i = 1; i <= N; i++) {
			if (indegree[i] == 0) {
				q.push(i);
			}
			dp[i] = time[i];
		}
		bool flag = false;
		while (!q.empty()) {
			int a = q.front();
			for (int i = 0; i < graph[a].size(); i++) {
				indegree[graph[a][i]]--;
				
				dp[graph[a][i]] = max(dp[a] + time[graph[a][i]], dp[graph[a][i]]);
				if (indegree[graph[a][i]] == 0) {
					q.push(graph[a][i]);
					if (graph[a][i] == des) {
						flag = true;
						break;
					}
				}
			}
			if (flag) break;
			q.pop();
		}
		cout << dp[des] << '\n';
	}
}