(C++) - 백준(BOJ) 1005번 : ACM Craft

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

1005번: ACM Craft

위상정렬 문제였습니다.

 

 

 

풀이방법

 1. 기존 위상정렬 문제처럼 x번을 지을 조건이 되면 바로 지을 수 있는 것이아닌 x번 건물의 선제조건인 건물들 중 건설시간이 가장 오래걸리는 건물이 다 지어져야 해당 건물을 지을 수 있습니다.

 

 2. 적절히 입력을 받습니다. 단 방향 그래프의 형태이며 인접리스트로 저장했습니다. 또한 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다. 의미는 그래프의 형태로 나타낸다면 x->y이므로 매번 건물순서를 입력받을 때 y의 진입차수를 증가시켜주었습니다.

 

 3. min heap을 이용합니다. 처음 진입차수가 0인 건물들은 모두 시작점이 될 수 있으므로 min heap에 넣어줍니다. 넣어줄 때는 pair {i번 건물건설시간, 건물번호 i} 의 형태로 push했습니다.

 

 4. 이 후 위상정렬을 시행합니다. 인접 노드의 진입차수를 1씩감소시켜주면서 만약 0이 되었다면 다음 건물을 지을 수 있는 조건이 되므로 다음 건물의 정보를 현재 건물의 건설시간에 더해 push해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int t, n, k, vic;
int buildTime[1001], ind[1001], update[1001];


int main(){
    cin >> t;
    while(t--){
        memset(buildTime,0,sizeof(0));
        memset(ind,0,sizeof(ind));
        memset(update,0,sizeof(update));

        cin >> n >> k;

        vector <vector<int>> graph(n + 1);

        for(int i = 1; i <= n; i++) cin >> buildTime[i];
        for(int i = 0,u,v; i < k; i++){
            cin >> u >> v;
            graph[u].push_back(v);
            ind[v]++;
        }

        cin >> vic;

        priority_queue <pii,vector<pii>,greater<pii>> pq;

        for(int i = 1; i <= n; i++){
            if(!ind[i]) pq.push({buildTime[i],i});
        }

        int ans = 0x3f3f3f3f;
        while(!pq.empty()){
            int cost = pq.top().first;
            int cur = pq.top().second;
            pq.pop();
            if(cur == vic) {ans = buildTime[cur]; break;}
            for(auto next : graph[cur]){
                ind[next]--;
                if(!ind[next]){
                    buildTime[next] += buildTime[cur];
                    pq.push({buildTime[next], next});
                }
            }
        }
        
        cout << ans << '\n';
    }
}