[백준(BOJ)] #1005- ACM Craft (파이썬, PyPy3)

문제

 

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

1005번: ACM Craft

 

---

문제 풀이

이 문제는 위상 정렬과 동적 계획법 알고리즘을 사용하여 해결할 수 있습니다.

 

2022.08.08 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 위상 정렬(Topology Sort)

[파이썬으로 배우는 알고리즘] 위상 정렬(Topology Sort)

2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

[파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

 

# 해당 노드까지 기존의 최소 건설 시간보다 연결된 노드와
# 해당 노드의 건설 시간을 합한 값이 더 크면 갱신
dp[connected_v] = max(dp[t] + time[connected_v], dp[connected_v])

 

 

풀이 과정을 보면서 자세히 알아보겠습니다.

풀이 과정

1) 1부터 6까지 번호가 적힌 건물 6개와 건설해야 할 건물의 번호는 6이라는 예시를 갖고 풀어보도록 하겠습니다. 먼저 입력으로 주어진 각 건물의 건설 비용을 담은 time 테이블, 그리고 동적 계획법을 적용시킬 dp 테이블을 준비합니다.

 

2) 진입 차수가 0인 건물을 큐에 삽입하면서(위상 정렬 참고) 해당 번호의 dp 테이블 값을 해당 번호의 time 테이블의 값으로 설정합니다. (해당 번호까지의 최소 건설 시간)

 

3) 1번 노드(1번 건물)를 큐에서 꺼내면서 연결되어 있는 2, 4번 노드의 dp 테이블 값을 위와 같이 갱신합니다. 각 노드 1의 최소 건설 시간과 해당 노드의 건설 시간을 더한 값으로 갱신함으로써 해당 노드까지의 최소 건설 시간을 의미합니다. 둘 다 기존 테이블 값인 0보다 크므로 갱신해줍니다.

 

4) 2번 노드를 큐에서 꺼내면서 연결되어 있는 3번 노드의 dp 테이블 값을 위와 같이 갱신합니다. 노드 2의 최소 건설 시간과 해당 노드의 건설 시간을 더한 값으로 갱신함으로써 해당 노드까지의 최소 건설 시간을 의미합니다. 기존 테이블 값인 0보다 크므로 갱신해줍니다.

 

5) 4번 노드를 큐에서 꺼내면서 연결되어 있는 5번 노드의 dp 테이블 값을 위와 같이 갱신합니다. 노드 4의 최소 건설 시간과 해당 노드의 건설 시간을 더한 값으로 갱신함으로써 해당 노드까지의 최소 건설 시간을 의미합니다. 기존 테이블 값인 0보다 크므로 갱신해줍니다.

 

6) 3번 노드를 큐에서 꺼내면서 연결되어 있는 6번 노드의 dp 테이블 값을 위와 같이 갱신합니다. 노드 3의 최소 건설 시간과 해당 노드의 건설 시간을 더한 값으로 갱신함으로써 해당 노드까지의 최소 건설 시간을 의미합니다. 기존 테이블 값인 0보다 크므로 갱신해줍니다.

 

7) 5번 노드를 큐에서 꺼내면서 연결되어 있는 6번 노드의 dp 테이블 값을 위와 같이 갱신합니다. 노드 5의 최소 건설 시간과 해당 노드의 건설 시간을 더한 값으로 갱신함으로써 해당 노드까지의 최소 건설 시간을 의미합니다. 기존 테이블 값인 20보다 크므로 갱신해줍니다. 

 

따라서 6번 건물까지의 최소 건설 완료 시간은 24가 됩니다.

 

---

구현

코드

import sys
input = sys.stdin.readline
from collections import deque

def topology():
    dq = deque()
    
    for i in range(1, n+1):
        if degrees[i] == 0:
            # dp 테이블 값 갱신
            dp[i] = time[i]
            dq.append(i)
    
    while dq:
        t = dq.popleft()     
        for connected_v in graph[t]:
            degrees[connected_v] -= 1
            # 기존의 dp 테이블 값보다 연결된 노드와 해당 노드의 건설 시간의 합이 더 크면 갱신
            dp[connected_v] = max(dp[t] + time[connected_v], dp[connected_v])
            if degrees[connected_v] == 0:
                dq.append(connected_v)

    print(dp[w])


if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        n, k = map(int, input().split())
        time = [0] + list(map(int, input().split()))
        graph = [[] for _ in range(n+1)]
        degrees = [0] * (n+1)
        dp = [0] * (n+1)
        
        for _ in range(k):
            s, e = map(int, input().split())
            degrees[e] += 1
            graph[s].append(e)
            
        w = int(input())
        
        topology()

결과