[백준] 1005번 ACM Craft (C++)

https://www.acmicpc.net/problem/1005

 

 

이 문제는 목표건물을 짓기 위해서 선행되는 관계에 따른 선행구조를 갖고 있기 때문에 

방향 비순환 그래프로 나타낼 수 있다.

 

즉 해당 목표건물을 짓기 위한 최소 시간을 알기 위해선 방향 비순환 그래프를 정렬하여

시작노드에서부터 목표노드까지의 시간을 계산하여 출력해야 한다.

 

이때 해당 노드를 짓기 위한 최소시간을 기록하기 위해서 배열을 하나 만들어주었고 

다음 건물을 건설할때마다 시간을 계속 누적해서 더하면서 update 시켜주었다.

 

 

따라서 시간복잡도는 O(V + E)

V : 노드

E : 간선의 수

V는 최대 1000 E는 최대 10만이기 떄문에 1억을 넘지 않는 수이기 때문에 통과가 가능하다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

int dx[] = {0, 1, -1, 0, 1, -1, -1, 1};
int dy[] = {1, 0, 0, -1, -1, 1, -1, 1};
int T, N, K, W;
int inDegree[1001];
int arr[1001];
int dp[1001];
vector<vector<int>> v(1001);

void topologySort() {			// 위상 정렬 수행
    queue<pii> q;

    for(int i = 1; i <= N; i++) {			// 진입 차수가 0인 노드 q에 push
        dp[i] = arr[i];
        if(inDegree[i] == 0) {
            q.push({i, arr[i]});
        }
    }

    while(!q.empty()) {
        int x = q.front().first;
        int t = q.front().second;
        q.pop();

        for(auto it : v[x]) {
            dp[it] = max(dp[it], t + arr[it]);			// 다음 노드로 갈때 걸리는 시간 update
            if(--inDegree[it] == 0) {
                q.push({it, dp[it]});
            }
        }
    }
}

void input() {
    cin >> T;

    while(T--) {
        cin >> N >> K;

        v.resize(N+1);

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

        for(int i = 0; i < K; i++) {
            int a, b;
            cin >> a >> b;
            inDegree[b]++;
            v[a].push_back(b);
        }

        cin >> W;

        topologySort();

        cout << dp[W] << endl;

        memset(inDegree, 0, sizeof(inDegree));
        memset(arr, 0, sizeof(arr));
        memset(dp, 0, sizeof(dp));
        v.clear();
    }
}

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

    input();
}