[BAEKJOON] 1005 ACM Craft (C++)

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

1005번: ACM Craft

문제

각각의 건물을 건설하는데 드는 시간, 건물이 지어져야하는 순서가 주어질 때, 특정 건물을 짓는데까지 소요되는 시간을 계산하는 문제이다.

 

풀이

topological sort 문제이다.

 

topological sort(위상정렬)을 이용하면, 특정한 순서가 있는 관계들을 순서대로 나열할 수 있다.

이 문제의 경우도 특정한 순서가 존재하기 때문에 위상정렬을 이용한다.

예를 들어 N->K라면 K건물 건설 이전에 N번 건물이 건설돼야 한다. 

 

W건물이 지어지는데 드는 최소 시간을 구하는 것이 목적인데, 최소시간이라고 해봐야 자기 자신과 연결된(자기 자신 이전에 먼저 지어져야하는) 건물이 모두 지어진 후에 건설을 시작할 수 있다.

따라서 자기 이전에 지어져야하는 건물들 중 가장 소요시간이 큰 값 + 자신을 짓는데 드는 시간으로 업데이트 한다.

-> 결국 DAG에서 Longest path를 찾는 문제와 유사하다.

 

그래프상으로 봤을 때는, 각각의 건물이 노드고, 해당 건물을 짓는데 걸리는 시간들을 간선의 가중치, 선행관계를 directed edge로 볼 수 있다.

 

위상정렬을 이번에 처음 배웠는데, 참 신기하다. 이래서 알고리즘을 배우나보다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <queue>
#define endl "\n"

using namespace std;

int N, K, W, T;
int D[1001];
int ans[1001];
int vcnt[1001];
vector<int> E[1001];
vector<int> topo;
queue<int> Q;
void Input() {
    int a, b;
    memset(D, 0, sizeof D); topo.clear(); 
    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> D[i]; E[i].clear(); ans[i] = 0; vcnt[i] = 0;
    }
    for (int i = 0; i < K; i++) {
        cin >> a >> b;
        E[a].push_back(b); vcnt[b] ++;
    }
    cin >> W;
}

void Solve() {

    for (int i = 1; i <= N; i++) {
        if (vcnt[i] == 0) {
            ans[i] = D[i];
            Q.push(i);
        }
    }

    while (!Q.empty()) {
        int n = Q.front(); Q.pop();
        topo.push_back(n);
        for (int i = 0; i < E[n].size(); i++) {
            if (--vcnt[E[n][i]] == 0) {
                Q.push(E[n][i]);
            }
            
        }
    }

    for (int i = 0; i < N; i++) {
        if (topo[i] == W) break;    
        for (auto k: E[topo[i]]) {
            ans[k] = max(ans[k], ans[topo[i]] + D[k]);
        }
    }
    cout << ans[W]<<endl;

}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("input.txt", "r", stdin);
    cin >> T;
    for (int i = 0; i < T; i++) {
        Input();
        Solve();
    }
    
    return 0;
}