[백준] ACM Craft

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

1005번: ACM Craft

위상정렬과 DP를 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

다음과 같이 건물들을 건설하는 게임을 하는데, 특정 건물을 건설하면 반드시 승리하게 됩니다. 이 때, 건물들 간에는 우선순위(규칙)이 정해져 있습니다. 특정 건물을 짓는데 걸리는 최소 시간을 return 해야 합니다. 

 

위 그림을 통해 간단하게 설명하면, 만약 4번건물을 짓는 최소시간을 구해야 한다면, 1->3&2->4 순서로 (10+100+10)120초가 걸리게 됩니다. 이 때, 4번건물을 위해서 2번 건물도 필요한데, 이 2번건물과 3번건물은 동시에 지어질 수 있기 때문에 100+1이 아닌 100초를 더해주는 것입니다. 자세한 내용은 문제를 직접 읽어보는 것을 추천합니다.

 

<Solution>

위상정렬을 사용해야 하는 것을 직감 할 수 있습니다.

 

그러면 어떻게 사용해야 할까요?

 

우선 알고리즘 부터 설명하고 이 알고리즘이 왜 성립하는지를 차차 더 설명해 보도록 하겠습니다. 

(dp[i] = i번 건물을 짓기 위한 최소 비용 으로 정의합니다)

1. 진입차수가 0인 것들을 deque자료구조로 관리하면서 기존의 위상정렬 알고리즘대로 진행합니다.
2. 이 때, 매번 화살표(경로)를 탐색할 때, dp값을 기존에 들어가 있던 값과, 현재 건물을 짓고 다음 건물을 짓는데 드는 비용을 합한 것 중 큰것을 선택합니다.

자 이 알고리즘이 왜 성립하는지 생각해봅시다. 

1번 과정은 우리가 흔히 생각하는 위상정렬의 과정과 동일하므로 넘어갑시다.

 

2번 과정은 위의 그림을 통해 살펴보면, 4번 건물을 짓기 위해서는 2번건물과 3번건물을 모두 지어야 합니다. 이 때, queue의 진행상태가 일반적인 위상정렬일 경우

[1] -> [2,3] -> [3] -> [4]

이렇게 진행되는 것을 유추 할 수 있습니다. 

 

이 때, 2번 건물이 pop되었을 때, 2번건물과 연결된 건물을 조회하면 4번건물이 나오고, 이 4번 건물의 현재 dp 상태는 아직 initialize된 이후 아무 변화가 없었으므로 0일 것입니다. 그렇다면, 0과 dp[2] + 10 = 21 중 더큰 21을 저장합니다. 

 

다음으로 3번 건물이 pop되었을 때, 3번건물과 연결된 건물을 조회하면 4번 건물이 마찬가지로 나오고, 4번 건물의 기존 dp인 21과 dp[3]+10 = 120중 더큰 120을 저장합니다. 

 

실제 구현은 아래와 같습니다.

import sys
from collections import deque

T = int(sys.stdin.readline().rstrip())

for _ in range(T):
    N, K = list(map(int,sys.stdin.readline().rstrip().split()))
    time = [0] + list(map(int,sys.stdin.readline().rstrip().split()))
    
    graph = [set() for _ in range(N+1)]
    degree = [0 for _ in range(N+1)]
    dp = [0 for _ in range(N+1)]

    # build graph and degree
    for _ in range(K):
        x, y = list(map(int,sys.stdin.readline().rstrip().split()))
        graph[x].add(y)
    for index, i in enumerate(graph):
        if index == 0:
            continue
        for i_ in i:
            degree[i_] += 1


    W = int(sys.stdin.readline().rstrip())
    # topology sort
    # first queue
    q = deque()
    for i, degree_ in enumerate(degree):
        if i != 0 and degree_ == 0:
            q.append(i)
            dp[i] += time[i]

    while(q):
        e = q.popleft()
        for i in graph[e]:
            degree[i]-=1
            dp[i] = max(dp[i], dp[e]+time[i])
            if degree[i] == 0:
                q.append(i)
    
    print(dp[W])