[BOJ] 백준 1005 ACM Craft

문제 링크

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

"모든 건물을 지을 수 없는 경우는 없다."라는 조건에서 주어진 그래프가 싸이클 없는 방향 그래프(DAG)라는 걸 알 수 있다. 건물을 짓는 순서가 정해져 있으므로 위상정렬로 해결할 수 있다. 단순 BFS로는 풀기 힘들다. 

본문의 예제를 단계별로 살펴보자.

$x$번 건물이 완성될 때까지의 총 시간을 $d[x]$으로 표현하겠다. 아직 완성 시간을 알 수 없는 건물은 0의 값을 가진다.

$step\,0)$

초기상태이다.

$n$	1	2	3	4
$d$	0	0	0	0

$step\,1)$

우선 1번 건물을 먼저 지을 수 있고, 10초가 걸린다.

$n$	1	2	3	4
$d$	10	0	0	0

$step\,2)$

2번과 3번을 동시에 지을 수 있다.

1번 건물이 10초 만에 지어졌으므로 2번 건물은 $10 + 1 = 11$초, 3번 건물은 $10 + 100 = 110$초 만에 지어진다.

$n$	1	2	3	4
$d$	10	11	110	0

$step\,3)$

2번 건물이 11초 만에 완성됐지만, 아직 3번 건물이 완성되지 않았으므로 4번 건물은 3번이 다 지어진 후에 지을 수 있다. 따라서 $110 + 10 = 120$초 만에 지어진다.

$n$	1	2	3	4
$d$	10	11	110	120

여기서 우리는 어떤 건물 $n$의 완성 시간을 구하기 위해 직전 단계에 필요한 건물들이 필요로 하는 총 시간 중, 가장 오래 걸리는 시간을 택해 $n$을 짓는데 걸리는 시간을 더해야 하는 것을 알 수 있다.

정답 코드

	#include <iostream>
	#include <queue>
	#include <vector>
	using namespace std;
	int t;
	int n, k, w;
	vector<vector<int> > p;
	vector<int> dist, times, indeg;
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> t;
	while (t--) {
	dist.clear();
	times.clear();
	indeg.clear();
	p.clear();
	cin >> n >> k;
	dist.resize(n + 1);
	times.resize(n + 1);
	indeg.resize(n + 1);
	p.resize(n + 1);
	for (int i = 1; i < n + 1; i++) {
	cin >> times[i];
	}
	for (int i = 0; i < k; i++) {
	int u, v;
	cin >> u >> v;
	p[u].push_back(v);
	indeg[v]++;
	}
	cin >> w;
	queue<int> q;
	for (int i = 1; i < n + 1; i++) {
	if (indeg[i] == 0) {
	q.push(i);
	dist[i] = times[i];
	}
	}
	while (!q.empty()) {
	int now = q.front();
	q.pop();
	if (now == w) break;
	for (int &next : p[now]) {
	if (--indeg[next]== 0)
	q.push(next);
	if (dist[next] < dist[now] + times[next]) {
	dist[next] = dist[now] + times[next];
	}
	}
	}
	cout << dist[w] << '\n';
	}
	}

view raw 1005.cpp hosted with ❤ by GitHub