[Baekjoon Online Judge] 백준 1005번 ACM Craft(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1005번 ACM Craft

(Python)

(글쓴날 : 2020.06.16)

 

---

* Baekjoon Online Judge, 백준 1005번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1005번 ACM Craft

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1005

1005번: ACM Craft

---

2) 풀이 과정

* 시간 복잡도 : O(E+V)

 

건물을 짓는 순서와 각 건물을 짓는데 걸리는 시간이 주어질 때, 특정 건물을 짓기까지 걸리는 최소 시간을 구하는 문제입니다.

 

저의 경우, 위상 정렬을 적용하였고, Python을 사용했습니다.

먼저 주어지는 정보들을 인접 리스트에 구현한 뒤, 위상 정렬을 적용해 건물을 짓는 테크트리를 찾아냈습니다.

위상 정렬을 수행하면서 찾은 테크트리 순서대로, 해당 건물을 짓기까지 가장 오래 걸린 시간을 기록해 나갔고, 최종적으로 건물 W를 짓는데 걸린 시간을 구해 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

from collections import deque
import sys
input = sys.stdin.readline
 
 
def topologicalSort():
    for _ in range(N):
        if not dq:
            return
 
        target = dq.popleft()
 
        for x in adjList[target]:
            sequence[x] = max(sequence[x], sequence[target] + D[x])
            indegree[x] -= 1
            
            if not indegree[x]:
                dq.append(x)
 
 
T = int(input())
 
for _ in range(T):
    N, K = map(int, input().split())
    D = [0] + list(map(int, input().split()))
 
    sequence = [0] * (N + 1)
    indegree = [0] * (N + 1)
    adjList = [[] for _ in range(N + 1)]
 
    for _ in range(K):
        X, Y = map(int, input().split())
 
        indegree[Y] += 1
        adjList[X].append(Y)
    
    W = int(input())
 
    dq = deque()
    for i in range(1, N + 1):
        if not indegree[i]:
            sequence[i] = D[i]
            dq.append(i)
 
    topologicalSort()
 
    print(sequence[W])

---