[백준][C++] 1005번: ACM Craft <211>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

1005번: ACM Craft

생각의 흐름

위상정렬을 이용한 문제이다. 이 문제를 풀어본 후 다음 문제도 풀어보기를 권장한다.

[백준][C++] 1766번: 문제집 <210>

이 문제는 위상정렬을 하면서 일의 순서를 정하는 과정에서 해당 일을 처리하는데 걸리는 최소시간을 구해야 한다.

따라서 totalTime[] 이라는 배열을 만들어, 해당 일을 처리하는데 걸리는 최소 시간을 저장하도록 만들었다.

=> totalTime[a] = b 의 의미는 "a번 건물을 짓는데 걸리는 최소시간은 b초입니다." 를 의미한다.

 

위상정렬이 동작하는 Queue의 반복문 안에서 위의 배열 값 또한 계속해서 갱신해 주면서 진행하였다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 1001

int T, N, K, W;
int inDegree[MAX];
int buildTime[MAX];
int totalTime[MAX];
vector<int> vec[MAX];

void init(){
    memset(inDegree, 0, sizeof(inDegree));
    memset(buildTime, 0, sizeof(buildTime));
    memset(totalTime, 0, sizeof(totalTime));
    for (int i = 0; i < MAX; i++) vec[i].clear();
}

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

    cin >> T;
    while(T--){
        cin >> N >> K;
        for(int i = 1; i <= N; i++) {
            cin >> buildTime[i];
        }
        for(int i = 0; i < K; i++) {
            int from, to;
            cin >> from >> to;
            vec[from].push_back(to);
            inDegree[to]++;
        }
        cin >> W;

        queue<int> Q;
        for(int i = 1; i <= N; i++){
            if(inDegree[i] == 0) {
                Q.push(i);
                totalTime[i] = buildTime[i];
            }
        }

        while(!Q.empty()) {
            int nowV = Q.front();
            Q.pop();

            for(int nextV : vec[nowV]) {
                inDegree[nextV] -= 1;
                totalTime[nextV] = max(totalTime[nextV], totalTime[nowV] + buildTime[nextV]);
                if(inDegree[nextV] == 0){
                    Q.push(nextV);
                }
            }
        }
        cout << totalTime[W] << "\n";
        init();
    }

    return 0;
}