백준 1005번 ACM craft _ 위상정렬 (c++)

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

1005번: ACM Craft

이 문제는 필자에게는 개인적으로 처음 백준 사이트에서 1000번(백준 첫 시작문제)부터 차례대로 차근차근 풀어가야지! 하고 시작했다, 이 사이트는 무슨 난이도랑 문제번호는 아무 상관없구나!를 깨닫게 해주는 뒤통수 빡 때리는 문제였다. 사실 단계별로 구분해놓은 것에도 41단계에 위치하는 난이도 19%대의 굉장히 어려운 문제이다. 하지만... 간혹 센스있는 친구들은 어떻게든 풀어내는 것 같다. (리스펙...)

결국 이 문제는 위상정렬을 활용하는 문제였다.

위상정렬이란, 위의 문제처럼 어떤 B라는 일을 하기 위해, A라는 일이 선행되어야 하는 것과 같이 순서가 정해져있는 작업에서 그 순서를 결정하기 위한 알고리즘이라고 생각하면 된다. 아래의 스타크래프트 테란 건물을 예시로 보자. 터렛을 짓기 위해선, 반드시 커멘드센터 -> 엔지니어링베이 -> 터렛 순서로 지어야 할 것이다. 이 문제에서는 이처럼 어떤 순서로 지어야 목표건물을 지을 수 있으며 그때 걸리는 최소시간을 출력하라는 것이다.

스타크래프트 건물 위상정렬

처음에는 나는 다음과 같이 문제를 뒤집어서 생각해보았다. (이건 틀린 접근입니다)

1. 어떤 건물이 바로 내 전 단계의 건물인가?
2. 그렇게 거꾸로 계속해서 나아가서, 시간들을 각자 path에 있는 것 끼리 더한 다음에 나중에 그 path들 중 최댓값을 구하자!

하고 나서 다음과 같이 알고리즘을 짰었다.

// 1. 목표건물을 먼저 짓는다. 전체 시간에서 목표건물의 공사시간 ++
// 2. 목표건물을 목적_build로 하는 기초_build를 짓는다. 기초_build의 공사시간을 더해준다.
// 3. Start_build를 dest_build로 하는 Start_build를 계속 지어간다.
// 4. 더 이상 지을 게 없으면 시간 카운트를 마친다.
// 5. 가장 시간이 오래 걸린 길을 pop한다.

이렇게 해서 예시까지 다 만족을 했건만...

백준 1005번 시간초과

계속되는 시간초과는 나를 멘붕에 빠트렸다..
문제는! 매 건물마다 무슨 건물이 나를 목적 건물로 하는지를 모든 RULE을 돌면서 체크를 한다는 것이었다.

이를 해결하기 위해서 우린 다시 돌아와서 위상정렬을 활용할 수 있다.
여기서 가장 key개념은 각각 건물마다 이 건물이 지어지기 위해 지어져야할 건물들의 수를 세어 indegree라는 벡터 리스트에 저장해놓는 것이다.
그리고 일일이 다 돌아보면서 찾아보는 것이 아니라 기초 건물에서 목적 건물로 방문 시마다 indegree 수를 -1씩 하면서 0이 되면 건설을 시작하게 하는 것이다.(기초가 되는 건물들이 다 지어지면 다음 건물 짓기 시작) 그리고 목적 건물을 지을 때는 기초 건물들 중 가장 시간이 오래걸렸던 건물을 기준으로 업데이트를 해준다. (다른 게 먼저 지어져도 가장 오래 걸리는 건물이 지어져야 다음 목적건물을 지을 수 있으니)
또한 시작할 때는 이전에 지어져야할 건물이 없는 건물(먼저 indegree가 0인 건물)을 Queue에 넣고 DFS(깊이 우선탐색)을 진행하였다.

코드는 다음과 같다.

#include <iostream>
#include <queue>
#include <vector>
#define MAX 1000
using namespace std;

int N_build, N_rule;
vector<int> Time_build;
vector<int> Start_build;
vector<int> Dest_build;
vector<int> indeg;
vector<int> timecount;
int win;

void input();

int main(){
    std::ios_base::sync_with_stdio(false);

    int N_test;
    cin>> N_test;
    for (int i=0; i<N_test; i++) {
        input();
        queue<int> Q; 
        for (int i=1; i<=N_build; i++){
            if (indeg[i]==0) Q.push(i);     // Q에 시작점을 다 집어넣음.
        }

        while(!Q.empty()){                  // Q가 빌 때 까지.
            int start = Q.front();          // Q의 제일 처음을 start로 저장.
            timecount[start] += Time_build[start];
            if (start == win) break;
            for (int i=0; i<N_rule; i++){   // start가 시작 빌딩에 있으면 매칭되는 목적 빌딩의 indegree를 1 차감.
                if (start == Start_build[i]){
                    indeg[Dest_build[i]]--;
                    if (timecount[Dest_build[i]] < timecount[start]){
                        timecount[Dest_build[i]] = timecount[start]; // 가장 시간이 오래걸린 애로 update.
                    }
                    if (indeg[Dest_build[i]] == 0) {
                        Q.push(Dest_build[i]); //indeg 0이면 Q에 추가.
                    }
                }
            }
            Q.pop();
        }
        cout << timecount[win] << "\n";
    }

    return 0;
}

void input(){
    Time_build.clear();
    Start_build.clear();
    Dest_build.clear();
    indeg.clear();
    timecount.clear();

    cin >> N_build >> N_rule;

    Time_build.resize(N_build+1);
    Start_build.resize(N_rule);
    Dest_build.resize(N_rule);
    indeg.resize(N_build+1);
    timecount.resize(N_build+1);

    for (int i=1; i<=N_build; i++) {cin>>Time_build[i];}
    for (int i=0; i<N_rule; i++) {
        cin>>Start_build[i]>>Dest_build[i];
        indeg[Dest_build[i]]++;
    }
    cin>>win;
}

 

끝.