2022.02.17 [백준] (python 파이썬) 게임 개발

 

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

1516번: 게임 개발

 

---

풀이

이 문제는 위상 정렬과 함께 다이나믹 프로그래밍을 사용해서 해결했다.

https://lee-ian.tistory.com/198

2022.02.17 [백준] (python 파이썬) ACM Craft

이 문제는 위의 블로그 문제와 거의 같은 문제이다.

from collections import deque
 
n=int(input())
#건물과 연결된 건물을 저장할 리스트
graph=[[] for i in range(n+1)]
#해당 건물보다 먼저 지어야할 건물 수를 저장할 리스트
check=[0]*(n+1)
#해당 건물까지 짓기 위한 거리를 저장할 리스트
distance=[0]*(n+1)
#해당 건물을 짓는 시간을 저장할 리스트
delay=[0]*(n+1)
 
for i in range(1,n+1):
    #입력 받은 문자열에 rstrip을 이용해서 -1을 잘라냄
    arr=list(map(int,input().rstrip('-1').split()))
    delay[i]=arr[0]
    #arr배열의 길이가 1이하면 해당 건물은 먼저 지어야 할 건물이
    #없으므로 if문을 타지않음
    if len(arr)>1:
        #arr이 1보다 크면 1번인덱스부터 끝까지 for문을 돌려
        #먼저 지어야할 건물을 graph에 저장하고 check증가시킴
        #여기서 arr에 저장된 정보는 먼저 지어야할 건물임
        #graph[먼저 지어야할 건물].append(나중에 지어야하는 건물)
        for a in range(1,len(arr)):
            graph[arr[a]].append(i)
            check[i]+=1
deq=deque()
for i in range(1,n+1):
    if check[i]==0:
        deq.append(i)
        #처음 check가 0이면 먼지 지어야하는 건물이 없으므로
        #해당 건물의 delay가 거리임
        distance[i]=delay[i]
 
while deq:
    a=deq.popleft()
    for i in graph[a]:
        if distance[i]==0:
            distance[i]=distance[a]+delay[i]
        else:
            #distance가 0이 아니면 먼저 지어야할 건물이 여러개이다.
            #이전 건물이 모두 지어야 해당 건물을 지을수 있으므로 
            #이전 건물의 지어지는 시간 중 가장 긴 시간을 저장함.
            distance[i]=max(distance[i],distance[a]+delay[i])
        check[i]-=1
        if check[i]==0:
            deq.append(i)
for i in range(1,n+1):
    print(distance[i])