[C++ 백준 풀이][Gold III] 1005번 : ACM Craft / 2623번 : 음악프로그램 (위상 정렬 응용)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 문제 '1005번 : ACM Craft'의 풀이 코드와 해설을 다룹니다.

 

문제의 난이도는 Solved.ac 기준 Gold III에 해당하며, 이 문제를 풀이하기 위해 위상 정렬의 개념이 사용됩니다.

 

 

1005번 : ACM Craft

 

문제가 길지만 요약해서 설명하자면, N개의 건물이 있고 이들에게는 특정 건물을 다른 건물보다 반드시 먼저 지어야 하는 규칙이 있을 때 최소 시간이 걸리도록 건설하기 위해서는 얼마의 시간이 필요한지 구하는 문제입니다.

예를 들어 K개의 규칙 중 하나로 1 3이 주어지면, 1번 건물을 반드시 3번 건물보다 먼저 지어야 한다는 뜻입니다.

 

2
4 4
10 1 100 10
1 2
1 3
2 4
3 4
4

 

위와 같은 입력이 주어졌다고 생각해봅시다.

그러면 4번 건물을 짓기 위해 2번 건물과 3번 건물을 동시에 지을 수 있고, 그 전에 1번 건물을 먼저 지어야 합니다.

1번 건물을 짓는데 10초가 걸리고, 2번 건물과 3번 건물을 동시에 지으면 더 오래 걸리는 3번 건물의 소요 시간에 의해 100초가 소모되며, 마지막 4번 건물을 짓는데 10초가 걸려서 총합 120초가 걸리게 됩니다.

따라서 120을 출력해주면 됩니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드는 아래 접은 글에 정리되어 있습니다.

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

int Max(int a, int b) { return a>b?a:b; }

int main() {
    int T, N, K, X, Y, W, pop, next, ans;
    scanf("%d", &T);
    for(int i=0; i<T; i++) {
        int degree[1005] = {0, }, D[1005] = {0, }, sum[1005] = {0, };
        vector<int> node[1005];
        queue<int> Queue;
        scanf("%d %d", &N, &K);
        for(int j=1; j<=N; j++) scanf("%d", &D[j]);
        for(int j=0; j<K; j++) {
            scanf("%d %d", &X, &Y);
            node[X].push_back(Y);
            degree[Y]++;
        }
        scanf("%d", &W);
        for(int j=1; j<=N; j++)
            if(!degree[j]) {
                Queue.push(j);
                sum[j] = D[j];
            }
        while(!Queue.empty()) {
            pop = Queue.front();
            Queue.pop();
            for(int j=0; j<node[pop].size(); j++) {
                next = node[pop][j];
                if(sum[pop]+D[next] > sum[next]) sum[next] = sum[pop]+D[next];
                degree[next]--;
                if(!degree[node[pop][j]]) Queue.push(next);
            }
        }
        printf("%d\n", sum[W]);
    }
}

 

문제를 해결하기 위해서는 위상 정렬의 개념을 알아야 합니다.

어떤 노드를 가리키는 선행 노드가 있을 때 선행 노드부터 처리를 해야 하므로, 자신을 가리키는 선행 노드가 없는 (위의 코드에서는 degree = 0에 해당하는) 노드를 먼저 제거해줍니다.

그 다음 노드와 연결된 간선을 제거하고 나서 새롭게 발생하는 degree = 0인 노드들을 다시 큐에 삽입하여 검사를 반복해줍니다.

 

이 문제는 단순히 위상 정렬로 순서를 출력하는 것이 아니라 시간의 총합을 구해야 하므로, 시간에 대한 점화식도 작성해야 합니다.

우선 값들을 sum[노드] = D[노드]로 초기화를 진행해줍니다.

그 다음 간단히 생각해보면 현재 노드와 현재 노드가 가리키는 다음 노드가 있을 때, 다음 노드까지 걸리는 시간의 총합은 현재 노드까지 걸린 시간 + D[다음 노드]와 다음 노드까지 걸리는 시간의 총합 중 더 큰 값이 될 것입니다.

따라서 이러한 방식으로 값을 갱신해서 문제를 풀어주면 sum[W]를 구할 수 있게 됩니다.

 

 

풀이를 제출해보면 220ms라는 짧지는 않은 시간에 모든 테스트케이스를 통과했음을 확인할 수 있습니다.

위상 정렬의 개념과 점화식을 둘 다 인지해야 했던 쉽지는 않은 문제였던 것 같습니다.

 

 

2623번 : 음악프로그램

 

이 문제는 따로 포스팅하려다가 그냥 같이 첨부합니다.

역시 위상 정렬을 이용하여 푸는 문제인데, 위의 문제에 비하면 쉬운 편에 속합니다.

여러 명의 순서가 동시에 나오면 이를 모두 만족하는 순서를 찾아 출력하고, 없으면 0을 출력하는 문제입니다.

간단히 큐를 이용해서 구현할 수 있습니다.

 

 

↓ 위의 이미지와 동일한 코드는 아래 접은 글에 정리되어 있습니다.

#include <cstdio>
#include <queue>
using namespace std;

int degree[1005] = {0, }, ans[1005], cnt = 0;
vector<int> node[1005];
queue<int> Queue;

int main() {
    int N, M, P, A, B, pop, next;
    scanf("%d %d", &N, &M);
    for(int i=0; i<M; i++) {
        scanf("%d %d", &P, &A);
        for(int j=0; j<P-1; j++) {
            scanf("%d", &B);
            node[A].push_back(B);
            degree[B]++;
            A = B;
        }
    }
    for(int i=1; i<=N; i++)
        if(!degree[i]) Queue.push(i);
    while(!Queue.empty()) {
        pop = Queue.front();
        ans[cnt++] = pop;
        Queue.pop();
        for(int i=0; i<node[pop].size(); i++) {
            next = node[pop][i];
            degree[next]--;
            if(!degree[next]) Queue.push(next);
        }
    }
    if(cnt != N) printf("0");
    else
        for(int i=0; i<cnt; i++) printf("%d\n", ans[i]);
}

 

코드를 보면 역시 Queue를 선언하고 node와 degree를 적절히 설정하여 선행 노드의 개수를 저장합니다.

이후 연결 관계를 어떻게 입력받느냐가 관건인데, 저의 경우에는 데이터의 수 P와 A를 동시에 입력받고 이후 B를 한 개씩 입력받으면서 A와 B 연결 → 기존의 B는 A로 저장, 새로운 B를 입력 받음 → 반복의 과정을 거쳐서 연결을 수행하였습니다.

나머지 과정은 일반적인 위상 정렬 문제의 풀이와 같습니다.

답이 없는 경우는 큐가 모두 비었는데도 Ans 배열이 다 차지 않았을 때를 조건으로 설정하였습니다.

 

 

제출해보면 시간이 거의 소모되지 않고 문제를 해결할 수 있음을 알 수 있습니다.