백준 1005 ACM Craft

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 w 건물을 짓는데 걸리는 최소 시간을 출력하는 문제입니다. 하나의 건물을 짓기위해서는 앞의 선행 건물들이 모두 지어져야 지을 수 있으므로 위상 정렬을 이용해야 합니다.

 

뭔가 계속 하나씩 코드를 잘못 적어서 무수하게 틀린 문제입니다 ㅠㅠ.. 우선은 벡터에 인접리스트 형식으로 각 정점과 연결되어 있는 정점들을 집어넣고 집어넣어지는 정점의 indegree를 하나씩 늘려줍니다. 위상정렬에서는 indegree가 0이 되는 곳이 선행자가 없는 가장 앞부분에 있는 정점입니다.

 

인접리스트와 indegree를 모두 완성 시킨뒤 indegree가 0인 점들부터 시작해서 다음 경로로 가장 길이가 길때를 찾아서 저장해 줍니다. (다익스트라와 비슷한 형식입니다.) 앞의 선행자들이 모두 완성돼야 다음 점이 건물을 지을 수 있으므로 최단 경로가 아닌 최장경로(?) 느낌 입니다.

 

경로는 변경 가능할때만 변경해주고 현재 정점에서 다음정점으로 비교를 했으므로 다음정점의 indegree를 하나 감소 시켜주고 이때 만약 indegree가 0이 된다면 다음정점을 q에 push해줍니다. 이러한 방식으로 q에 목표건물인 w가 push 될 때까지 반복해준뒤 dist[w] + time[w]를 해주면 결과를 얻을 수 있습니다. dist[w]는 w의 건설을 시작 할 수 있는 최단시간을 의미합니다. 따라서 이시간에 time[w]를 더해주면 끝입니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> v[1001];
queue<int> q;
int time[1001];
int dist[1001];
int indegree[1001];
int w;
void craft() {
	while(!q.empty()) {
		int f = q.front();
		if(f == w)
			break;
		q.pop();
		for(int i = 0; i < v[f].size(); i++) {
			if(dist[v[f][i]] < dist[f] + time[f] )  
				dist[v[f][i]] = dist[f] + time[f];
			
			indegree[v[f][i]]--;
			if(indegree[v[f][i]] == 0)
				q.push(v[f][i]);
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int T; cin >> T;
	int N, K;
	while(T--) {
		for(int i = 1; i < 1001; i++)
			v[i].clear();
		fill_n(time, 1001, 0);
		fill_n(dist, 1001, 0);
		fill_n(indegree, 1001, 0);
		while(!q.empty())
			q.pop();
		cin >> N >> K;
		for(int i = 1; i <= N; i++)
			cin >> time[i];
		for(int i = 1; i <= K; i++) {
			int x1,x2; cin >> x1 >> x2;
			v[x1].push_back(x2);
			indegree[x2]++;
		}
		cin >> w;	
		for(int i = 1; i <= N; i++)
			if(indegree[i] == 0) 
				q.push(i);
		craft();	
		cout<<dist[w] + time[w]<<'\n';
			
	}
	return 0;
}