[BOJ] 1005. ACM Craft (C++)

문제

건설 순서 규칙이 주어졌을 때, 특정 건물을 가장 빨리 지을 때까지 걸리는 최소시간 구하기

생각할 것

• 순서 규칙이 있으므로 위상정렬 사용해보기
• 처음 시작할 때 진입차수가 0인 것이 여러개 있다면 여러번 실행해봐야하는가!?
  • 이런식으로 하면 진입차수 0인것과 연결된 정점 모두 판단 못함
• 정점번호마다 누적된 건설 시간을 더하고 비교하면서 최댓값을 넣기

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T, N, K, X, Y, W;
    cin >> T;

    while (T--) {
        // 입력
        cin >> N >> K;

        vector<int> time(N + 1);
        for (int i = 1; i <= N; i++) {
            cin >> time[i];
        }

        vector<vector<int>> adj(N + 1);
        vector<int> inDegree(N + 1);
        for (int i = 0; i < K; i++) {
            cin >> X >> Y;
            adj[X].push_back(Y);
            inDegree[Y]++;
        }

        cin >> W;

        // 진입 차수가 0인 정점 큐에 넣기, 시간 초기화
        queue<int> q;
        vector<int> build(N + 1);
        for (int s = 1; s <= N; s++) {
            if (inDegree[s] == 0) {
                int totalTime = 0;
                q.push(s);
            }
            build[s] = time[s];
        }

        // 위상정렬
        for (int i = 1; i <= N; i++) {
            if (q.empty()) continue;
            int cur = q.front();
            q.pop();

            for (int j = 0; j < adj[cur].size(); j++) { // 현재 정점과 연결된 정점
                int next = adj[cur][j];
                build[next] = max(build[next], build[cur] + time[next]); // 더 큰 시간을 넣기
                if (--inDegree[next] == 0) {
                    q.push(next);
                }
            }
        }

        cout << build[W] << endl;
    }

    return 0;
}