[백준] 1005번 ACM Craft(C++)

1005번: ACM Craft (acmicpc.net)

1005번: ACM Craft

---

난이도 : 골드 3

 

풀이 방법 :

 

위상정렬 + dp 문제

 

ans라는 배열에 각 건물 시간 걸리는거 저장해놓고 

위상정렬 돌릴 때

특정건물을 짓기위한 시간 = 건물을 짓기위해 지어야 되는 건물 중 가장 오래걸리는 시간 + 특정건물 걸리는 시간

if (ans[now] + time[next] > ans[next]) {
ans[next] = ans[now] + time[next];
}

을 해주면 된다. 

 

 

+

58%에서 틀렸습니다가 계속 나와서 결국 답을 봤는데 next를 방문했을 때 진입차수를 -1해주는 걸

ans[next]값이 달라질 때만 -1 해줘서 계속 틀렸다.. 

굳이 if문안에 넣을 필요가 없었다.. 갱신되면 갱신되는대로, 안되는대로 위상정렬은 돌아가는 거니까 

 

아직까지도 좀 헷갈리긴한데 ... 어렵네 ㅠ

 

코드 :

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

int t;
int main() {
	cin >> t;
	while (t--) {
		int n, k, d[1002], w, ans[1002];
		vector<int> v[1002];
		int len[32002] = { 0, };
		queue<int> q;
		cin >> n >> k;
		for (int i = 1; i <= n; i++) {
			cin >> d[i];
			ans[i] = d[i];
		}
		int x, y;
		for (int i = 0; i < k; i++) {
			cin >> x >> y;
			v[x].push_back(y);
			len[y]++;
		}
		for (int i = 1; i <= n; i++) {
			if (len[i] == 0) q.push(i);
		}
		cin >> w;

		while (!q.empty()) {
			int now = q.front();
			q.pop();
			for (int i = 0; i < v[now].size(); i++) {
				int next = v[now][i];
				if (ans[now] + d[next] > ans[next]) {
					ans[next] = ans[now] + d[next];
				}
				len[next]--; //if문 안에 넣으면 안됨!! 
				if (len[next] == 0) {
					q.push(next);
				}
			}
		}

		cout << ans[w] << "\n";

	}

}