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

문제링크 : https://www.acmicpc.net/problem/1005

1005번: ACM Craft

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, N, K, W;
int X, Y;
vector<int>t, inDegree, result;
vector<vector<int>>graph;
queue<int>q;

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

    cin >> T;
    while(T--)
    {
        cin >> N >> K;
        
        t.resize(N+1); t.clear();
        inDegree.resize(N+1); inDegree.clear();
        result.resize(N+1); result.clear();
        graph.resize(N+1); graph.clear();
        
        for(int i=1; i<=N; i++)
        {
            cin >> t[i];
        }
        while(K--)
        {
            cin >> X >> Y;
            graph[X].push_back(Y);
            inDegree[Y]++; //진입 차수 증가 (X가 우선)
        }

        cin >> W;
        for(int i=1; i<=N; i++) //진입차수가 0인 정점들을 큐에 삽입
        {
            if(inDegree[i]==0) q.push(i);
            result[i]=t[i];
        }

        while(!q.empty()) //큐가 비면 사이클 발생이므로 종료
        {
            int cur = q.front(); //현재 방문 노드
            q.pop();
            for(int i=0; i<graph[cur].size(); i++) //인접한 노드들의 진입 차수를 1씩 줄이고, 0이면 다시 큐에 삽입
            {
                int next = graph[cur][i];
                result[next] = max(result[next], result[cur] + t[next]); //작업시간 갱신
                if(--inDegree[next]==0) q.push(next);
            }
        }
        cout << result[W] << "\n";
    }

    
    return 0;
}

위상정렬 문제이다.

기본적인 틀은 전에 풀었던 2056번 작업 문제와 비슷하므로 해당 문제 링크를 첨부하였다.

https://blob-thinking.tistory.com/282

[백준 2056번] 작업 (C++)

 

여기서 조금 다른 것은 해당 문제는 W에 해당하는 건물에 도달하는 시간이 필요하다는 것이다.

이는 result[next] = max(result[next], result[cur] + t[next]로 인해 저장되므로, 출력 시에 result[W]를 출력해주면 된다.

 

그리고 테스크 케이스가 여러가지이므로 매 테스트케이스 마다 사용한 벡터들을 초기화 해주어야 한다.