[백준 1005] ACM Craft

작성일 | In |

문제 링크

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

풀이

처음에 건물 건설에 조건이 없는 건물들을 짓기 시작한다고 생각해봅시다. 건물 $i$는 $D_i$에 건물이 완성될 것이고 건물 $i$를 지은 다음에 지을 수 있는 건물 $j$는 최소한 $D_i$ 이후에 지을 수 있습니다. 조건이 없는 건물들을 모두 지은 이후에는 “조건이 없는 건물들을 짓는 것”이 선행 조건이었던 건물들을 지을 수 있게 되고 지을 수 있는 가장 빠른 시간을 알고 있기 때문에 그 건물 $x$는 $mx_x + D_x$에 완성될 것이고 건물 $x$를 지은 다음에 지을 수 있는 건물 $y$는 최소한 $mx_x + D_x$이후에 지을 수 있습니다. 이를 건물 $w$에 도달할 때까지 반복한다면 $w$가 완성될 시간 $mx_w + D_w$를 알 수 있습니다.

하지만 건물 $i$를 짓기 위해 지어야 하는 건물들이 모두 지어졌는지 어떻게 확인할 수 있을까요? 문제에 나와있는 사진처럼 그래프의 관점에서 보면 정점(건물)에 향해있는 간선(indegree)에 연결된 건물을 지어서 모두 $mx_i$를 갱신했다면 그 건물을 지을 수 있음을 알 수 있습니다. 그러므로 정점 $i$를 향해있는 간선의 수를 $p_i$로 저장한다면 $mx_i$를 갱신할 때마다 $p_i$에 1을 빼는 것을 반복하다가 $p_i$가 0이 되었을 때 건물을 짓기 시작하면 되고 건물 $i$를 짓는 것이 선행조건 이었던 건물 $j$의 $mx_j$를 $mx_i + D_i$로 갱신합니다.

이를 BFS를 이용해 구현하면 되는데, 일반적으로 구현하는 방법처럼 도달했을 때 큐에 넣는 것이 아니고 마지막으로 방문했을 때 큐에 넣는다고 생각하고 구현하면 됩니다. 시간복잡도는 BFS를 하는 데에 걸리는 시간 $O(N+M)$입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int tc, n, m, w;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> tc;
    while(tc--){
        cin >> n >> m;
        vector<int> d(n+1), p(n+1), v[n+1], mx(n+1);
        for(int i=1;i<=n;i++) cin >> d[i];
        for(int i=1;i<=m;i++){
            int x, y; cin >> x >> y;
            v[x].push_back(y), p[y]++;
        }
        cin >> w;
        queue<int> q;
        for(int i=1;i<=n;i++) if(!p[i]) q.push(i);
        while(!q.empty()){
            int u = q.front(); q.pop();
            for(int x : v[u]){
                mx[x] = max(mx[x], mx[u] + d[u]);
                if(--p[x] == 0) q.push(x);
            }
        }
        cout << mx[w] + d[w] << "\n";
    }
}