백준 No.1005 [ACM craft]

Baekjoon Online Judge No.1005 [ACM craft]

---

  문제 

1005번: ACM Craft (acmicpc.net)

1005번: ACM Craft

---

  설명 

  위상정렬(2021.08.05 - [Algorithm (C++ based)/Algorithm 이론] - 위상 정렬 (Topological Sort))의 기본 개념을 이용하여 풀 수 있는 문제이다. 위상정렬을 통해 각 건물(노드)에 방문을 할 때 마다 그 건물을 짓는데 걸리는 시간을 계속해서 최대값으로 업데이트를 한다. 어떠한 건물을 짓기 위해선 이전 노드에 해당되는 건물들을 전부 지어야 하고, 이전 건물들을 전부 짓는데 걸리는 시간은 결국 가장 오래 걸리는 시간이기 때문이다.

  정렬을 완료한 후 문제에서 요구하는 건물을 짓는데 걸리는 시간은, 최종적으로 업데이트 된 해당 건물을 짓는데 걸리는 시간을 출력하면 된다.

 

01234

 

  문제에 주어진 테스트 케이스중 하나를 예시로 구현을 해 보았다. 각 노드별로 아래에 적힌 숫자는 그 건물을 짓는데 걸리는 시간이다. 그 시간은 계속해서 최대값으로 업데이트가 되고, 최종적으로 그 건물을 짓는데 걸리는 최소 시간이 된다.

---

  Code 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> outdegree;
vector<int> indegree;
vector<int> fee;
vector<int> dp;
int tc, v, e, tar;

int solve() {
	queue<int> q;

	for (int i = 1; i <= v; i++)
		if (indegree[i] == 0) q.push(i); // 입력간선 0인 애들 push

	int cur = 0;
	int next = 0;
	int size = 0;

	while (!q.empty()) {
		cur = q.front(); q.pop(); // queue의 맨 앞 node 를 뽑았다.

		if (cur == tar)
			return dp[tar];

		// 현재 node 의 outdegree 개수 만큼 check
		size = outdegree[cur].size();
		for (int i = 0; i < size; i++) {
			next = outdegree[cur][i];
			if (--indegree[next] == 0) q.push(next);

			dp[next] = max(dp[next], dp[cur] + fee[next]);
		}
	}
}

void init() {
	int start, end;
	for (int i = 1; i <= e; i++) {
		cin >> start >> end;

		indegree[end]++;
		outdegree[start].push_back(end);
	}

	cin >> tar;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> tc;

	while (tc--) {
		cin >> v >> e; // v is 건물, e is 간선, tar is 목적지

		outdegree.assign(v + 1, vector<int>(v + 1, 0));
		indegree.assign(v + 1, 0);
		fee.assign(v + 1, 0);
		dp.assign(v + 1, 0);

		for (int i = 1; i <= v; i++) {
			cin >> fee[i]; // i'th 건물을 짓는데 드는 비용
			dp[i] = fee[i];
		}

		// 건물 짓는 순서를 입력
		init();
		cout << solve() << '\n';

		outdegree.clear();
		indegree.clear();
		fee.clear();
		dp.clear();
	}
}