[BOJ] 1005 ACM Craft

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

1005번: ACM Craft

알고리즘: 위상 정렬

 

시간복잡도: O(n^2)

 

 

접근:

1. 건물 짓는 순서가 정해져 있음.

2. 각각의 건물들은 선행 건물들이 모두 지어져야 건설 가능.

 

Point: 순서, 선행(prev.) -> 위상 정렬

 

최종 시간복잡도: O(n^2)

 

 

 

#include<iostream>
#include<vector>
#include<queue>
#define MAX(a, b) (((a)>(b))?(a):(b))
using namespace std;
int T, N, K, X, Y, W, h;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> T;
	
	while(T--)
	{
		cin >> N >> K;
		
		vector<int> D(N), p(N), TimeTable(N);
		vector<int> b[N];
		queue<int> Q;
		for (int i = 0; i < N; i++)
			cin >> D[i];
		for (int i = 0; i < K; i++)
		{
			cin >> X >> Y;
			p[Y-1]++;
			b[X-1].push_back(Y-1);
		}
		
		cin >> W;
		
		for (int i = 0; i < N; i++)
		{
			if (!p[i])
			{
				Q.push(i);
				TimeTable[i] = D[i];
			}
		}
		
		while(!Q.empty())
		{
			h = Q.front();
			Q.pop();
			
			for (int i : b[h])
			{
				p[i]--;
				TimeTable[i] = MAX(TimeTable[i], TimeTable[h] + D[i]);
				if (!p[i])
				{
					Q.push(i);
					p[i]--;		//check
				}
			}
		}
		cout << TimeTable[W-1] << "\n";
	}
	return 0;
}