[Python] 백준 / gold / 1005 : ACM Craft

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

오랜만에 위상정렬 문제를 복습했다. 저번에 한 번 공부를 하고, 위상정렬은 inDegree 를 이용해서 푼다 고 기억을 해둬서 수월 하게 풀렸던 거 같다. 그런데 진짜 inDegree 만 기억나서 BFS 를 적용하는게 맞나 헷갈리기도 했다.

저번에 풀었던 위상 정렬 문제 : https://velog.io/@heyksw/Python-백준-gold-1766-문제집

"문제집"이 더 어려웠던 이유는 BFS 과정에서 큐가 아닌 힙을 사용해야 되기 때문이다. 위상 정렬에서는 inDegree 가 0 인 값들을 큐에 삽입하게 되는데, 문제집에서는 큐에 삽입한 원소 중에서도 값이 작은 원소를 먼저 꺼내야 했다.

ACM Craft 에서는 visit 을 도입해서 방문처리를 해줘야 한다는게 까다로운 조건이였던거 같다. (근데 생각해보니 visit 을 도입 안해도 풀 수 있을 거 같다.)

기억할 것 : 위상정렬은 inDegree table + BFS 로 푼다.

파이썬 코드

from collections import deque
import copy
import sys
T = int(sys.stdin.readline())


def program():
    N, K = map(int, sys.stdin.readline().split())
    time = [-1]
    inputTime = list(map(int, sys.stdin.readline().split()))
    time = time + inputTime
    graph = [[] for _ in range(N+1)]
    cost = copy.deepcopy(time)
    visit = [False] * (N+1)
    inDegree = [0] * (N+1)
    start = []
    for _ in range(K):
        X, Y = map(int, sys.stdin.readline().split())
        graph[X].append(Y)
        inDegree[Y] += 1
    W = int(sys.stdin.readline())

    for i in range(1, N+1):
        if inDegree[i] == 0:
            start.append(i)

    q = deque()
    for i in start:
        q.append((i, time[i]))

    while q:
        now, t = q.popleft()

        for x in graph[now]:
            if not visit[x]:
                cost[x] = t + time[x]
                visit[x] = True
            else:
                cost[x] = max(cost[x], t + time[x])

            inDegree[x] -= 1
            if inDegree[x] == 0:
                q.append((x, cost[x]))

    print(cost[W])


for _ in range(T):
    program()