BOJ 1005. ACM Craft

BOJ 1005. ACM Craft

랭크 : 골드3

문제 풀이

위상 정렬로 풀면 되는데, 시간 순서에 맞게 행동하도록 우선 순위 큐를 활용해서 문제를 해결하였습니다. 시간 초과를 몇번 냈는데, 테스트 케이스가 여러번 인데 초기화를 제대로 안해줘서 생겼습니다. dfs와 dp로 푸는 방법도 존재하는데, 만들어야 하는 건물부터 아래로 내려가면서 시간을 중첩시켜 나가는 방법으로 풀 수 있습니다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int status[1001];
int timetable[1001];
vector<vector<int>> board(1001, vector<int>());

int main() {
    fastio;
    int tmp, T, N, K, W, num1, num2;
    cin >> T;
    while (T--) {
        cin >> N >> K;
        for (int i=1; i <= N; i++) {
            cin >> tmp;
            timetable[i] = tmp;
            status[i] = 0;
            board[i].clear();
        }

        for (int i=0; i < K; i++) {
            cin >> num1 >> num2;
            board[num1].push_back(num2);
            status[num2]++;
        }
        cin >> W;
        priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int, int>>> q;
        for (int i=1; i <= N; i++) {
            if (status[i] == 0) {
                status[i] == -1;
                q.push(make_pair(timetable[i], i));
            }
        }

        int passedTime = -1;
        while (status[W] != -1) {
            passedTime = q.top().first;
            int next = q.top().second; q.pop();
            status[next] = -1;
            for (int i=0; i < board[next].size(); i++) {
                if (--status[board[next][i]] == 0) {
                    q.push(make_pair(timetable[board[next][i]] + passedTime, board[next][i]));
                }
            }
        }
        cout << passedTime << endl;
    }
}

 

알고리즘	시간복잡도	공간복잡도
Topology Sort	O(N \log N)	O(N ^ 2)