[C++] 백준/Gold/1005. ACM Craft

문제: ACM Craft (백준 1005번)

문제 분석

문제 개요:
각 건물마다 건설에 걸리는 시간이 주어지고, 특정 건물을 짓기 위해 먼저 지어져야 하는 건물들의 관계(선행 조건)가 주어진다.
목표는 주어진 목표 건물 W를 짓기 위한 최소 건설 시간을 구하는 것이다.

 

핵심 아이디어:

• 위상 정렬:
  선행 조건을 고려한 건설 순서를 결정하기 위해 위상 정렬을 사용한다.
  indegree(진입 차수)를 활용해 선행 조건이 없는 건물부터 처리한다.
• DP (동적 계획법):
  각 건물을 짓기 위한 최소 시간을 dp 배열에 저장한다.
  특정 건물의 최소 건설 시간은, 해당 건물에 선행하는 모든 건물들의 건설 시간 중 최대값에 현재 건물의 건설 시간을 더한 값이다.
  (즉, 선행 건물 중 가장 늦게 완공되는 시점을 고려하여 건물을 지어야 한다.)

---

해결 방법

1. 입력 처리:
   • 건물 개수 N, 건물 간의 관계 개수 K를 입력받고, 각 건물의 건설 비용(cost) 배열과 관계(그래프)를 구성한다.
   • 또한, 각 건물의 진입 차수(indegree)를 기록한다.
2. 위상 정렬:
   • 진입 차수가 0인 건물부터 큐에 넣어 위상 정렬을 진행한다.
   • 정렬된 순서(sortedGraph)에 따라 건물들을 차례대로 처리하며, 다음 건물들의 진입 차수를 감소시킨다.
3. DP 진행:
   • 위상 정렬 순서대로 건물을 처리하면서, 해당 건물을 짓기 위한 최소 시간을 계산한다.
   • 각 건물에 대해, 선행 건물(refGraph)을 확인하여 이미 계산된 dp 값 중 최대값을 구한 후, 현재 건물의 비용(cost)를 더한다.
4. 출력:
   • 목표 건물 W의 dp 값을 출력한다.

코드 전체

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0);
    
    int T, N, K, W; 
    cin >> T;
    
    while (T--) {
        // 입력 처리
        cin >> N >> K;
        vector<vector<int>> graph(N + 1), refGraph(N + 1);
        vector<int> cost(N + 1), indegree(N + 1);
        
        for (int i = 1; i <= N; i++) {
            cin >> cost[i];
        }
        for (int i = 0; i < K; i++) {
            int a, b; 
            cin >> a >> b;
            graph[a].push_back(b);
            refGraph[b].push_back(a);
            indegree[b]++;
        }
        cin >> W;
        
        // 위상 정렬
        vector<int> sortedGraph;
        queue<int> q;
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0)
                q.push(i);
        }
        
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            sortedGraph.push_back(node);
            for (const int& next : graph[node]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
        }
        
        // DP: 각 건물을 짓기 위한 최소 시간 계산
        vector<int> dp(N + 1, 0);
        for (int i = 0; i < sortedGraph.size(); i++) {
            int node = sortedGraph[i];
            int maxTime = 0;
            // 해당 건물의 선행 건물들 중 최대 건설 완료 시간을 찾음
            for (const int& ref : refGraph[node]) {
                maxTime = max(maxTime, dp[ref]);
            }
            dp[node] = maxTime + cost[node];
        }
        
        cout << dp[W] << '\n';
    }
    
    return 0;
}