[그래프, 난이도 중상] 백준 1005번 ACM Craft

 

이 문제는 위상 정렬을 이용하여 풀어야 한다.

위상 정렬이란 자신을 가리키는 노드들이 전부 자신 노드에 방문을 했을 때 다음 노드로 이동할 수 있게 하는 알고리즘이다. 즉, 진입차수가 0인 노드들을 큐에 넣으며 시작하고, 큐에서 꺼낸 노드의 인접노드의 진입 차수를 1씩 감소시키며, 이 결과로 진입 차수가 0이 된 노드들을 다시 큐에 넣는 과정을 반복하는 알고리즘이다. 

 

이전 건물을 다 짓기 전까지는 현재 건물을 짓지 못한다는 조건이 있으므로 위상 정렬을 이용해야 한다는 것이다.

 

그리고 시간 초과가 나지않게 동적계획법(DP)도 병행하였다. 위상정렬을 수행하며, 이 건물(노드)을 짓는데 걸리는 누적 시간을 업데이트 해주는 것이다. 이전 건물들이 모두 세워져야 현재 건물을 세울 수 있기 때문에 max함수를 이용하여 업데이트 해주었다. 자신을 가리키는 노드가 여러 개일 때 그 갯수만큼 누적시간정보가 들어올텐데 그중 max값을 DP값으로 정했다는 의미다.

 

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
int indegree[1001];
int createtime[1001];
int d[1001];
vector<int> a[1001];
queue<int> q;
int n, k, m, ans;
int maxi(int a,int b){
	if(a>b) return a;
	else return b;
}
int mini(int a,int b){
	if(a<b) return a;
	else return b;
}
void bfs(){
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<a[x].size();i++){
			int y=a[x][i];
			d[y]=maxi(d[y],d[x]+createtime[y]);
			indegree[y]--;
			if(indegree[y]==0){
				q.push(y);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int test;
	cin >> test;
	for(int t=0;t<test;t++){
		memset(d,0,sizeof(d));
		memset(createtime,0,sizeof(createtime));
		memset(indegree,0,sizeof(indegree));
		ans=0;
		for(int i=0;i<1001;i++){
			a[i].clear();
		}
		int n,k,victory;
		cin >> n >> k;
		for(int i=1;i<n+1;i++){
			cin >>  createtime[i];
		}
		for(int i=1;i<k+1;i++){
			int x,y;
			cin >> x >> y;
			a[x].push_back(y);
			indegree[y]++;
		}
		cin >> victory;
		for(int i=1;i<n+1;i++){
			if(indegree[i]==0){
				d[i]=createtime[i];
				q.push(i);
			}
		}
		bfs();
		cout << d[victory] << "\n";
	}
}