백준 1005 ACM Craft - 골드3 [파이썬]

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

1005번: ACM Craft

 

DP를 곁들인 위상정렬 문제이다.

지난번에 풀었던 선수과목 문제랑 상당히 비슷했다.

 

2차원 배열로 graph를 쓰는 것 대신 collections의 defaultdict를 사용해보았다.

그런데 이것은 상당히 느렸다. 그냥 좀 더 타이핑 쳐서 2차원 배열로 하는게 나을 것 같다.

 

그리고 sys를 import 해놓고서 input = sys.stdin.readline 하는걸 잊어먹었는데도 잘 돌아가더라.

input()이 어쨌든 원래 있는 함수라 그랬다.

코드를 추가해주니 확연히 빨라졌다.

 

소스코드

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

TC = int(input())
for tc in range(TC):
    N, K = map(int, input().split(" "))
    indegree = [0 for i in range(N+1)]
    result = [0 for i in range(N+1)]
    # graph = defaultdict(list)
    graph = [[] for i in range(N+1)]
    time = [0]
    tmp = list(map(int, input().split(" ")))
    for i in tmp:
        time.append(i)

    for k in range(K):
        a, b = map(int, input().split(" "))
        graph[a].append(b)
        # 진입차수
        indegree[b] += 1

    queue = deque()
    for i in range(1, N+1):
        if indegree[i] == 0:
            queue.append((i, time[i]))  # idx num, time
            result[i] = time[i]

    while queue:
        now, nowtime = queue.popleft()
        for i in graph[now]:
            indegree[i] -= 1
            result[i] = nowtime + time[i] if nowtime + \
                time[i] >= result[i] else result[i]
            if indegree[i] == 0:
                # queue.append((i, nowtime + time[i]))
                queue.append((i, result[i]))

    answerNum = int(input())
    print(result[answerNum])

# 위상정렬 + DP

 

result[i]로 갱신 해준걸 계속해서 들고 queue에 들어가야하는데,

그것을 잘못 생각해서 틀렸었다. (주석되어있는게 틀린코드)

 

defaultdict 쓰고, input = sys.stdin.readline 안해주었던게 944ms 이고

defaultdict 빼고 위 코드 넣어준게 592ms 이다.