백준 1005 AMC Craft

www.acmicpc.net/problem/1005

1005번: ACM Craft

1005번 위상정렬 

위상 정렬이란 방향 그래프의 꼭짓점들의 방향을 거스리지 않고 정렬을 할 수 있는 알고리즘이다. 

 

이 알고리즘은 dfs, stack와 queue를 활용하여 이러한 알고리즘을 해결 할 수 있다. 

 

stack으로 해결할 경우 각 정점이 어떤 위치에서 연결되었는지를 알 수 없어 이문제에서는 적당하지 못했다. 얘를 들어 아래와 같은 그래프가 있을 수 있다.

스택의 경우 반복문을 통해 비어있으면 dfs를 사용하여 체크해주는데 만약 3이 아니라 1을 방문하게 되면 체크 후 스택에 들어가고 다른 곳으로 이동하지 못한다. 즉 움직이는 순서를 알 순 있어도 각각이 어떤 rank로 연결되어 있는지 알 수 없는 것이다. 

 

하지만 queue의 경우에는 다른 점이 있다. 

 

queue의 경우에는 각각의 정점에 얼마나 많은 정점이 들어오는지를 체크하여 만약 들어오는 정점이 없는경우 위 사진과 같은 경우에는 3이 시작점이 되어서 위상 정렬을 할 수 있다. 이렇게 알맞은 시작점을 고르는데에는 queue를 활용한 방법이 조금 더 어울려 보였다. 

 

그런 다음 dp를 활용해야하는데 이 점은 간단했다. 처음 queue에서 pop하는 정점의 경우에는 

 

아래와 같은 점화식을 통해 가볍게 해결했다. 

 

dp[now] = max(dp[now], value[now]);

 

그리고 새로운 정점을 발견할 때는 아래와 같은 점화식으로 해결해주었다. 

 

dp[next] = max(dp[next], dp[now] + value[next]);

 

코드

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

void solve();
void torpologySort(vector<int> vc[], vector<int> ingreed[]);

int main(){
	int T;
	scanf("%d", &T);
	for(int i = 0; i < T; i++){
		solve();		
	}

}

int dp[1002] = {0, };
int value[1002] = {0, };
int N, K, W;
void solve(){
	vector<int> vc[1002], ingreed[1002];
	memset(dp, -1, sizeof(dp));
	memset(value, 0, sizeof(value));

	int start, end;
	scanf("%d %d", &N, &K);
	
	for(int i = 1; i <= N; i++)
		scanf("%d", &value[i]);
	

	for(int i = 0; i < K; i++){
		scanf("%d %d", &start, &end);
		vc[start].push_back(end);
		ingreed[end].push_back(start);
	}

	scanf("%d", &W);

	torpologySort(vc, ingreed);

	printf("%d\n", dp[W]);
}

void torpologySort(vector<int> vc[], vector<int> ingreed[]){
	queue<int> qu;
	for(int i = 1; i <= N; i++){
		if(ingreed[i].size() == 0)
			qu.push(i);
	}

	while(!qu.empty()){
		int now = qu.front();
		qu.pop();
		dp[now] = max(dp[now], value[now]);
		for(auto next : vc[now]){
			dp[next] = max(dp[next], dp[now] + value[next]);
			ingreed[next].pop_back();
			if(ingreed[next].size() == 0)
				qu.push(next);
		}
	}
}