[c++] 백준 1005: ACM Craft

1005번: ACM Craft

문제

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define fio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;

int main(){
    fio;
    int t, n, k, w;
    cin >> t; // t = testcase 수

    for (int a = 0; a < t; a++){
        int indegree[1001] = {0, };
        int buildTime[1001] = {0, };
        vector<int> order[1001]; // order = 건설 순서
        queue <int> route;
        /**
         * input
        */
        cin >> n >> k; // n = 건물의 개수, k = 건물 간의 건설순서 규칙 개수
        int d[n + 1];  // d = 건물 건설 시간
        for (int i = 1; i <= n; i++) {
            cin >> d[i];
        }
        
        int x, y;                // x -> y : 건설 순서
        for (int i = 1; i <= k; i++) {
            cin >> x >> y;
            order[x].push_back(y); // x에 대한 다음 건설 건물 y list
            indegree[y]++;
        }
        cin >> w; // w = 건설 번호
        
        /**
         * solution
        */

        for (int i = 1; i <= n ; i++){
            if (indegree[i] == 0){
                route.push(i);
                buildTime[i] = d[i];
            }
        }    

        while (route.empty() == 0){
            int current = route.front();
            route.pop();

            for (int i = 0; i < order[current].size(); i++){
                int next = order[current][i];
                buildTime[next] = max(buildTime[next], buildTime[current] + d[next]);
                indegree[next]--;

                if (indegree[next] == 0){
                    route.push(next);
                }
            }

            
        }

        cout << buildTime[w] << "\n";
    }
    
}

해설

위상정렬에 관한 알고리즘을 처음 접한 문제였다. 위상정렬이란 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘이다.

해당 문제는 먼저 건설해야하는 건물을 다 건설해야 그 다음 건물을 건설할 수 있는 문제였다. 따라서 건설 순서를 order에 저장한 후 각 건물이 지어지기 전에 필요한 건물 수를 indegree에 추가적으로 저장해준다.

order[x].push_back(y); // 건물 x에 대한 다음 건설 건물 y list
indegree[y]++; // y가 지어지기 전에 만들어져야 할 건물 수

모든 입력값을 저장한 후, indegree 값이 0인 것을 route에 넣어 먼저 건물을 건설해주는 순서를 정한다. 그리고 해당 건물 건설 소요시간을 buildTime에 저장한다.

for (int i = 1; i <= n ; i++){
            if (indegree[i] == 0){
                route.push(i);
                buildTime[i] = d[i];
            }
} 

그 후 route의 첫 번째 요소를 뽑아 다음 건설할 건물을 next에 받은 후 이를 건설하는 시간을 계산한다. 이 때, 원래 존재하는 건물의 건설시간과 새로 추가할 건설시간을 비교해 더 많이 걸리는 시간을 저장해준다. 그리고 indegree값을 1 줄여주는 과정을 반복한다. 그 후 indegree값이 0이면 route에 넣어 다음 건물을 건설할 수 있다. route에 있는 모든 건물 건설 시간을 모두 계산하고, 원하는 w 건물에 대해 건설 시간을 출력하면 된다.

while (route.empty() == 0){
	int current = route.front();
  route.pop();

  for (int i = 0; i < order[current].size(); i++){
	  int next = order[current][i];
    buildTime[next] = max(buildTime[next], buildTime[current] + d[next]);
    indegree[next]--;

    if (indegree[next] == 0){
	    route.push(next);
    }
  }
}

...

cout << buildTime[w] << "\n";