백준 1516 게임개발 파이썬 풀이

난이도 : 골드3

풀이일 : 05066

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

1516번: 게임 개발

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

import sys
from collections import deque

N = int(sys.stdin.readline().strip())
time = [0] * N    # 개별 건물 건설 시간
total = [0] * N    # 개별 건물 누적 시간
count = [0] * N    # 선행 건물 개수
building = [[] for _ in range(N)]    # 선행 건물 종류

for i in range(N):
    t, *temp = map(int, sys.stdin.readline().split())
    time[i] = t
    for j in temp:    # -1 아닌 요소에 대해 선행 건물 정보 저장
        if j > 0:
            count[i] += 1
            building[j-1].append(i)

queue = deque()    # 선행 건물이 없다면, queue 추가, 시간 저장
for i in range(N):
    if not count[i]:
        queue.append(i)
        total[i] = time[i]

while queue:    # 건설 작업, 시간은 누적 시간 중 큰 값으로 재할당
    x = queue.popleft()
    for y in building[x]:
        count[y] -= 1
        total[y] = max(total[y], total[x] + time[y])
        if not count[y]:    # 선행건물이 모두 지어진 건물은 queue 추가
            queue.append(y)

for i in total:    # 모든 건물의 누적시간 출력
    print(i)

코드 구성

• time : 개별 건물 건설 시간 
• total : 개별 건물의 선행건물 건설 시간을 포함한 누적 건설 시간
• count : 선행 건물 개수
• building : 해당 건물을 선행 건물로 하는 건물 종류
• queue : 선행 건물이 없는 건물 
• 정보 입력 받을 때, 요소의 개수가 제각각이므로 *패킹 연산자 사용
• 2차원 배열 building으로 남은 선행 건물 개수를 줄여나가며 누적 시간은 큰 값으로 재할당
• 선행 건물이 사라진 건물들은 queue 추가로 건설

---

느낀점

맨 처음 입력 받을 때, *패킹 연산자로 입력받은 temp를 사용해 count[i], building[j-1]을 정보를 저장할 때 대충 넘어가서 최종 출력을 해보고 안 맞는 부분을 고쳤다.

내가 하고 있는 작업에 대한 결과를 논리적으로 생각하고 접근해서 맞는지 꼼꼼하게 확인하는 과정을 거치자