[백준]1516 게임개발

1. 풀이

(1) 입력값

아래의 두 리스트로 그래프를 관리한다

parent[i] : i 노드로 들어오는 노드들을 저장한 리스트

garph[i]: i노드에서 향하는 노드들을 저장한 리스트

이후 정석대로 간선을 삭제한 후, parent[i]가 비어있는 노드들을 차례대로 q에 넣어서 탐색한다.

​

(2) 위상정렬

이때 각 노드의 최소완료시간을 구해야 하기 때문에

ans[toNode]=max(ans[nowNode]+time[toNode],ans[toNode])를 수행해 주어야 한다.

ans[i] : i건물까지 만드는데 드는 최소시간

time[i] : i건물을 만드는데 드는 시간

q에서 뽑힌 노드 i의 ans[i]는 최소시간으로 보장된상태이다. 그리고 ans[nowNode]+time[toNode]가 ans[toNode]보다 크다면, toNode를 짓기 이전에 nowNode까지 건설하는데 드는 시간이 추가로 더해져야 하는것을 의미한다.

(또한 이전까지 지어져야 할 건물 중 가장 오래걸리는 것을 기준으로 잡아야 하므로 max를 이용해야한다. )

(Ex : 1(10분)->2 ,3(12분)->2 일때 2는 12분 후에 건설이 시작될 수 있음.)

​

2.소스코드

from collections import deque
N=int(input())
time=[0 for i in range(N+1)]
ans=[0 for i in range(N+1)]
parent={}
graph={}
q=deque([])
for i in range(1,N+1):
    parent[i]=[]
    graph[i]=[]
for i in range(1,N+1):
    temp=list(map(int,input().split()))
    time[i]=temp.pop(0)
    temp.pop()
    size=len(temp)
    if size==0:
        q.append(i)
        ans[i]=time[i]
    for j in range(size):
        fromNode=temp[j]
        graph[fromNode].append(i)
        parent[i].append(fromNode)

while(q):
    nowNode=q.popleft()
    for toNode in graph[nowNode]:
        parent[toNode].remove(nowNode) #끊기
        ans[toNode]=max(ans[nowNode]+time[toNode],ans[toNode])
        if not parent[toNode]:
            q.append(toNode)


for i in range(1,N+1):
    print(ans[i])