[백준] 1005: ACM Craft

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

1005번: ACM Craft

백준 초창기 문제라서 그런지 우리 학교의 요소가 등장하는 문제이다. 그저 반갑

하지만 문제는 착하진 않다. 헷갈릴 만한 요소가 많았고, 질문 게시판을 보면서 답을 찾아나갈 수 있었다.

이 문제는 위상정렬(탐색) +  다이나믹 프로그래밍(해당 건물까지 도달하기에 필요한 최소 시간을 구하기)를 결합한 문제였다.

처음에 풀 때는 선후 관계가 있다는 점에 위상 정렬이라는 점을 파악하였으나, 최소 소요 시간을 구할 때는 다이나믹 프로그래밍으로 풀면 고민하는 문제가 해소된다는 것을 나중에야 알았다.

FAQ

1. 먼저 지어야하는 건물부터 규칙이 주어진다는 보장이 없다.

그래서 모든 규칙을 입력받기 전까지는 무엇을 먼저 해야하는지 알 수 없고 규칙을 입력받으면서 문제를 해결해나갈 수 없다.

모든 규칙을 입력받은 뒤에 계산을 해야 한다.

 

2. 1번 건물을 가장 먼저 지어야 한다는 보장도 없다. 건물의 번호는 그저 번호이고 순서와는 아무런 상관이 없다.

그리고 먼저 지어야하는 건물이 여럿일 수도 있다. 위상정렬 시에 습관적으로 1번부터 짓는 관습이 있는데, 이는 엄밀히 조건이 아니다.

 

3. 이 문제는 일반적인 DFS, BFS로 풀 수 없다.💡

• BFS
  처음 지어야 하는 건물들부터 시작해서 어떤 건물을 짓기까지 거쳐야 하는 규칙의 수가 다 다를 수 있기 때문이다. 
  (즉 그래프 노드의 parent가 하나가 아니라 다수이다.) 따라서 일반적인 BFS로는 풀이가 불가능하고, BFS를 변형하여 어떤 건물의 선행 건물이 모두 지어지면 Queue에 넣어서 처리하는 것도 유효한 풀이 방법 중 하나이다.
• DFS
  도착점부터 역으로 찾아가볼까라는 생각이 들지만, 한 번 방문한 건물에 대해 재계산을 하는 것이 비효율적이다.

4. 재귀 탐색 시에는 초기값을 0으로 설정하면 안된다. 왜냐하면 건물을 짓는 데 0만큼 소요되는 경우도 존재하기 때문

5. 테스트케이스마다 초기화를 잘하자.

 

처음에는 동시에 여러 건물을 지을 수 있다고 해서 한 그래프의 level마다 나누어서 최대 소요 시간만을 추가하였다.

하지만 만약 방문할 필요 없는 노드들이 있으면 불필요한 시간이 포함된다.

따라서 level마다 시간을 처리하는 것이 아니라 DP로 노드마다 최소 소요 시간을 계산해야 한다.

 

나한테 유용했던 반례)

1
10 5
1 2 3 4 5 6 7 8 9 10
1 6
2 7
3 8
4 9
5 10
6

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> result;
int main(void) {
    int t;
    cin >> t;
    while(t--) {
        int n, k, a, b, w;
        int q_idx = 0;
        bool is_over = false;
        vector<int> indegree(1001, 0);
        vector<vector<int>> construction(1001);
        queue<int> q;
        vector<int> time_dp(1001, 0);
        int time[1001];
        cin >> n >> k;

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

        for(int i = 0;i < k;i++) {
            cin >> a >> b;
            construction[a].push_back(b);
            indegree[b]++;
        }
        cin >> w;

        for(int i = 1;i <= n;i++) {
            if(!indegree[i]) {
                q.push(i);
                time_dp[i] = time[i];
            }
        }

        while(!is_over) {
            while(!q.empty()) {
                int cur = q.front();
                q.pop();

                if(cur == w) {
                    is_over = true;
                }

                for(auto next : construction[cur]) {
                    if(time_dp[next] < time_dp[cur] + time[next]) {
                        time_dp[next] = time_dp[cur] + time[next];
                    }
                    if (--indegree[next] == 0) {
                        q.push(next);
                    }
                }
            }
        }
        result.push_back(time_dp[w]);
    }

    for(auto r: result) {
        cout << r << '\n';
    }
}