백준 1005 - ACM Craft

백준 1005 문제 바로가기

풀이

• 정점을 작업(task)이라고 했을 때, indegree(진입차수)가 0이 아닌 작업들은 선행되어야 하는 다른 작업들이 모두 끝나야 비로소 수행될 수 있다.
• 따라서 초기에 indegree(진입차수)가 0인 모든 정점을 큐에 넣는다.
• 큐에서 꺼낸 정점(now)이 향하고 있는 정점(next)의 indegree를 1감소시켰을 때, 값이 0이면 큐에 넣는다.
• 다음 정점(next)에 도달하는데 소요되는 시간이 현재(now) 위치의 정점에서 소요되는 시간보다 크도록 갱신한다.

소스 코드

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int T;
int N;//건물 수
int K;//건설 순서 규칙 개수


int initTime[1001];
int totalTime[1001];

vector<int> adj[1001];
int indegree[1001];

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    cin >> T;
    for (int tc = 0; tc != T; ++tc) {
        cin >> N >> K;
        for (int num = 1; num <= N; ++num) {
            cin >> initTime[num]; // num 건물을 짓는데 소요되는 시간
            totalTime[num] = initTime[num];

            // init
            adj[num].clear();
        }
        for (int i = 0, X, Y; i != K; ++i) {
            cin >> X >> Y; // X를 지은 후 Y를 짓는것이 가능
            adj[X].push_back(Y);
            ++indegree[Y];
        }

        queue<int> q;
        for (int num = 1; num <= N; ++num) {
            if (indegree[num] == 0) {
                q.push(num);
            }
        }

        while (!q.empty()) {
            int now = q.front();
            q.pop();
            for (int next : adj[now]) {
                if (--indegree[next] == 0) {
                    q.push(next);
                }
                totalTime[next] = max(totalTime[next], totalTime[now] + initTime[next]);
            }
        }

        int W;
        cin >> W;
        // 건물 W를 건설완료 하는데 드는 최소 시간
        cout << totalTime[W] << '\n';
    }
    return 0;
}