[백준] 1005 ACM Craft (Python 파이썬)

문제 설명

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

1005번: ACM Craft

---

풀이 과정

위의 그림과 같은 상황이 있을 때,

4를 건설하기 위해서는 반드시 1 -> 2 -> 4의 순서로 건설되거나 1 -> 3 -> 4의 순서로 건설되어야 하기 때문에

선수 관계를 표현할 때 이용하는 위상정렬 알고리즘을 이용한다.

 

그리고, 1 -> 2 -> 4 경로는 건설시간이 총 21초가 걸리고

1 -> 3 -> 4 경로는 건설시간이 총 120초가 걸리는데

4를 건설하기 위해서는 2와 3이 모두 완료되어야 하기 때문에

2가 빨리 끝나더라도 3이 끝날 때 까지 기다려야 한다.

그래서 4를 건설하기 까지는 1 -> 3 -> 4의 소요시간인 120초가 소요된다.

 

이를 통해 알 수 있는 것은, 어느 한 지점에 들어오는 경로가 두 개 이상이라면 그 경로중 최댓값을 저장한다는 것이다.

이 부분은 DP를 이용해 두 경로 중 최댓값을 저장하는 방식을 이용하면 된다.

 

이 문제의 핵심은 위상정렬을 사용하되, 위상정렬을 하는 과정에서 DP를 이용해 최댓값을 저장해 나간다는 점이다.

 

이를 파이썬으로 작성한 코드는 다음과 같다.

코드 중 리스트d는 입력값으로 인덱스0부터 시작하므로

1부터 시작하는 인덱스와 맞춰주기 위해 i-1을 적용하였다.

import sys
from collections import deque

t = int(sys.stdin.readline())

for _ in range(t):
    n, k = map(int, sys.stdin.readline().rstrip().split())
    d = list(map(int, sys.stdin.readline().rstrip().split()))
    graph = [[] for _ in range(n + 1)]
    inDegree = [0 for _ in range(n + 1)]
    dp = [0 for _ in range(n + 1)]
    queue = deque()

    for i in range(k):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        graph[a].append(b)
        inDegree[b] += 1

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

    for i in range(1, n + 1):
        if inDegree[i] == 0:
            queue.append(i)
            dp[i] = d[i - 1]

    while queue:
        tmp = queue.popleft()

        for i in graph[tmp]:
            inDegree[i] -= 1
            dp[i] = max(dp[i], dp[tmp] + d[i - 1])
            if inDegree[i] == 0:
                queue.append(i)

    print(dp[w])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !