[BOJ] 1005_ACM Craft(Python)

문제

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

풀이

사용한 알고리즘 : DP, 위상정렬, BFS

 

가장 먼저 최적화 된 건설 시간을 구하기 위해 indegree=0인 노드에서 탐색을 시작한다.  

이후, bfs나 dfs 등 원하는 방법으로 탐색하며 해당 노드의 indegree를 1씩 줄이다가 0이 되면 queue에 넣는다.

indegree가 0이라는 것은 더 이상 해당 건물 건축 시간이 갱신되지 않는 다는 것을 뜻하게 된다.

그렇기에, 원하는 건물 w가 나왔을 때 정답을 리턴하여 계산을 좀 더 최적화 했다.

 

다만... 이번 문제는 알고리즘이 아닌 입력을 받는 방식에서 시간 초과가 생겼었고, 입력 받는 함수를 input()에서 sys.stdin.readline()으로 교체한 뒤 테스트를 통과할 수 있었다.

 

 

 

 

코드

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

def bfs(queue):
    while queue:
        node, time = queue.popleft()
        time += build_time[node]
        if node == w:
            return time
        max_time[node] = time
        next_list = graph[node]
        for next_node in next_list:
            max_time[next_node] = max(max_time[next_node], time )
            in_cnt[next_node] -= 1
            if in_cnt[next_node] == 0:
                queue.append([next_node,max_time[next_node]])
    return -1


for __ in range(t):
    n,k = map(int,sys.stdin.readline().split())
    max_time = [0]*(n+1)
    build_time = [0]+list(map(int,sys.stdin.readline().split()))
    in_cnt = [0]*(n+1)
    graph = {i+1:deque() for i in range(n)}
    
    for __ in range(k):
        f,t = map(int,sys.stdin.readline().split())
        graph[f].append(t)
        in_cnt[t] += 1
    w = int(sys.stdin.readline())
    print(bfs(deque([[i,0] for i, cnt in enumerate(in_cnt[1:], start = 1) if cnt == 0])))