[ 백준 - 1005 ] ACM Craft (Python)

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

1005번: ACM Craft

문제 그림만 봐도 위상정렬이라고 생각이 들었다.

마지막 건물을 짓기 위해서는 해당 건물이 필요로 하는 건물들이 필요한데 아마 스타크래프트 같은 게임을 생각하면 편할 것 같다.

팩토리를 짓기 위해서는 배럭이 필요한 느낌?

 

근데 각 건물들에는 짓는데 걸리는 시간이 있어서 A를 건설하기 위해서 B, C가 있다면 B, C가 둘 다 완성되어야 A를 지을 수 있기 때문에 최장 시간 걸리는 건물의 시간을 기록하면 된다.

 

[ 📌 사전에 정의할 것 ]

• 시간(time): 건물들의 시간을 담는 리스트 (건물의 번호에 맞게 관리하기 위해서 리스트 이용)
• 그래프(Graph): 각 건물들의 빌드 순서가 있기 때문에 관계를 나타내는 단방향 그래프 
• 진입차수(indegree): 위상정렬을 풀기 위해서 필요한 진입차수
• ans: 각 건물에 도달하는데 걸리는 최종 시간

 

[ 📌 코드 흐름 ]

1. 진입 차수가 0인 건물들을 queue에 담고, 위상정렬을 시작한다.

2. 연결되어 있는 진입차수를 끊어 주면서 다음 건물을 짓는 시간이 다음 건물까지 짓는 시간 + 현재 건물에서 해당 다음 건물까지의 시간중 큰 값을 기록한다. ===>  max(ans[cur_node] + time[linked_node], ans[linked_node])

 

위 과정을 반복하면 우리가 얻고자하는 최종 건물의 시간이 리스트에 기록된다.

 

 

[ 📌 코드 - Python ]

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

T = int(input())

def topology_sort():
    while queue:
        cur_node = queue.popleft()

        for linked_node in graph[cur_node]:
            indegree[linked_node] -= 1
            ans[linked_node] = max(ans[cur_node] + time[linked_node], ans[linked_node])

            if indegree[linked_node] == 0:
                queue.append(linked_node)
        

for _ in range(T):
    N, K = map(int, input().strip().split())
    time = [0] + list(map(int, input().strip().split()))
    graph = [[] for _ in range(N + 1)]
    indegree = [0 for _ in range(N + 1)]
    ans = [0 for _ in range(N + 1)]
    queue = deque()

    for _ in range(K):
        X, Y = map(int, input().strip().split())

        graph[X].append(Y)
        indegree[Y] += 1

    for idx in range(1, N + 1):
        if indegree[idx] == 0:
            queue.append(idx)
            ans[idx] = time[idx]

    topology_sort()
    target = int(input())
    print(ans[target])

 

개인적으로는 로직보다 시간이 더 많이 들었던 곳은 필요한 자료구조를 잡고 입력 값 세팅하는 앞쪽 부분이 아니였나 싶다.