[백준] 1005 - ACM Craft

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

1005번: ACM Craft

그래프 문제를 풀고 싶어서, solved.ac의 그래프 태그 문제를 찾아보다가 발견한 문제이다.

스타크래프트를 연상시키는 문제인데, 그래프에 DP를 섞은 재미있는 문제였다.

---

우선 이 문제는 문제에서 주어진대로 시작하는 건물부터 차근 차근 건물을 지어나가다가

마지막에 원하는 건물을 짓게되면 멈추는 풀이로는 접근이 쉽지가 않다.

 

그래서 거꾸로 원하는 건물을 짓기 위해 지어야 하는 건물들을 역탐색하는 과정으로 문제를 바꿔보았고,

이렇게 바꾸면 주어진 조건보다 간단하게 그래프를 그릴 수 있게 된다.

 

또한

 

이런 케이스의 경우도 쉽게 풀 수 있게 된다.

이 케이스는 별도의 그래프 탐색 없이 바로 답이 나온다.

---

이 아이디어를 기반으로 이제 그래프를 탐색해야 하는데,

처음에는 '최소시간 = 최단 경로 => BFS' 가 떠올라서

BFS로 푸는 방법을 열심히 고민했지만, BFS 풀이를 놓고 2번 예제를 보니

굉장히 비효율적인 풀이 방식임을 알게 되었다.

 

 

이 예제를 그래프로 그려보면 다음과 같다.

 

그림 퀄리티가 낮아서 죄송합니다..

 

우선 이 그래프를 탐색할 때 BFS방식으로 탐색하게되면, 방문체크를 할 수 없게 된다.

그 이유는 BFS를 사용할 경우, 노드의 방문 순서가

5 - 4 - 3 - 2 - 1

이렇게 되는데, 이렇게만 방문하면,

4, 3, 2 노드의 최단 건설 시간을 알 수 없게 된다.

따라서 리프노드를 만날 때 까지 탐색해야 계산이 되므로

 

5 - 4 - 3 - 2 -1

4 - 3 - 2 - 1

3 - 2 - 1

2 - 1

1

순으로 반복해서 방문해야만 한다.

그런데 이렇게 놓고보니 구조가 반복되는 것을 알 수 있다.

1을 방문해서 1번 건물을 짓는 시간을 알았다면,

2번 건물을 짓는 시간도 알 수 있게 되고,

그걸로 3번 건물을 짓는 시간도 알 수 있게되는 구조가 반복되는데

여기에서는 한번 계산했던 최단 건물 건설 시간을, 반복해서 계산해야만 한다.

 

여기에서 DP를 써야겠다고 느꼈고, 어떻게 해야

'한번 결정한 임의 노드의 최단 건설 시간을 기록해서 재사용할 수 있을까' 를 고민하게 되었다.

 

따라서 생각을 틀어 DFS로 이 그래프를 탐색해보고자 했다.

그러면 노드의 방문 순서는 이렇게 된다.

5 - 4 - 3 - 2 - 1

 

BFS랑 겉보기에는 똑같아 보이지만, 사실은 전혀 다르다.

BFS는 이렇게 노드를 방문한다.

5번 건물을 지으려면, (4, 3, 2, 1) 건물을 지어야 한다.

라는 의미로 생각할 수 있다.

이 문장만으로는 4, 3, 2, 1 번 건물에 대해서는 아무 정보를 얻을 수 없다.

그래서 4, 3, 2, 1번 건물에 대해서도 일단 다시 방문해야만 한다.

 

DFS는 이렇게 노드를 방문한다.

5번 건물을 지으려면 4번 건물을 지어야 해

근데 4번 건물 지으려면 3번 건물 지어야 하고,

근데 3번 건물 지으려면, 2번 건물 지어야 하고,

근데 2번 건물 지으려면 1번 건물 지어야 하고,

1번 건물 지을 땐 그냥 바로 지을 수 있어

 

로 풀어서 쓸 수 있다.

그리고 이렇게 방문한다면 DP를 쓸 수 있게 된다.

 

저렇게 방문한 결과 1번 건물의 건설 시간을 알 수 있고

2번 건물의 건설 시간 중, 1번 건물의 건설 시간 정보는 기록된 걸 가져와 알 수 있게 된다.

 2 -> 1 이라는 반복 방문을 피할 수 있게 된 것이다.

 

이렇게 2번 건물의 건설 시간을 알게 되었다면

3번 건물의 건설 시간인

max (2번 건물의 건설시간, 1번 건물의 건설시간)

역시 기록한 값으로 부터 바로 구할 수 있게 된다.

 

이를 코드로 구현하면 다음과 같이 된다.

---

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = 9876543210

def find_min_time(building):
    max_time = 0 # must_build 중 가장 큰 값이 이 건물의 최소 건설 시간
    for must_build in graph[building]:
        if min_build_time[must_build] < INF:
            time = min_build_time[must_build]
        else:
            time = find_min_time(must_build)
        max_time = max(max_time, time)

    # building의 최소 건설 시간 = 자기를 짓기 위해 필요한 건물들 중 최대 건설 시간 + 자신의 건설 시간
    min_build_time[building] = min(min_build_time[building], max_time + build_time[building])
    return min_build_time[building]


T = int(input())
for _ in range(T):
    #input
    n, k = map(int, input().split())
    build_time = [0] + list(map(int, input().split()))
    min_build_time = [INF for _ in range(n+1)]

    graph = [[] for z in range(n+1)]
    for __ in range(k):
        before_build, to_build = map(int, input().split())
        graph[to_build].append(before_build)

    build_goal = int(input())

    # DFS
    answer = find_min_time(build_goal)

    # answer
    print(answer)

DFS의 재귀적 방문과, top-down 방식의 DP가 재귀적 풀이를 사용하는 것의 공통점을 활용한 문제였다.