Python 백준 알고리즘 1516 : 게임 개발

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

1516번: 게임 개발

 

# 1516 게임 개발

from collections import defaultdict, deque

n = int(input())
ans = [0] * (n+1)
# 건물을 짓는데 필요한 시간
time = [0] * (n+1)
# 진입차수 
degree = [0] * (n+1)
q = deque()
# 간선표현
graph = defaultdict(list)

#위상 정렬 알고리즘
for i in range(1, n+1) :
  build = list(map(int,input().split()))
  time[i] = build[0] 

  for j in build[1:-1] :
    graph[j].append(i) # j -> i
    degree[i] += 1 # j -> i 이기에 진입차수에 1을 더해줌

for i in range(1, n+1) :
  # 진입차수가 0인 건물을 큐에 넣음
  if degree[i] == 0 :
    q.append(i)
    ans[i] = time[i]

# bfs 탐색
while q :
  now = q.popleft()
  for i in graph[now] :
    degree[i] -= 1
    # 제일 오래 걸리는 건물을 짓는데 필요한 시간으로 ans값을 구함
    ans[i] = max(ans[i], time[i] + ans[now])
    if degree[i] == 0 :
      q.append(i)

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

 

상단에 collection 모듈의 defaultdict을 사용하면 key 값이 존재하지 않아도 내부적으로 디폴트 값을 줄 수 있어 key 값을 1로 초기화하는 작업을 생략할 수 있다. 위에 코드에서는 간선을 표현하기 위해 사용했다.

 

그리고 이 문제에서 건물은 동시에 여러 개를 지을 수 있기 때문에, 어떠한 건물을 짓기 위해 필요한 건물들 중에서 짓는데 가장 오래 걸리는 건물의 시간만 고려하면 되기 때문에 건물들을 노드라고 볼 때, 진입차수를 낮춰가며 정렬하는 위상 정렬 알고리즘을 사용해야 한다.

 

https://freedeveloper.tistory.com/390

[이것이 코딩 테스트다 with Python] 36강 위상 정렬

 

위상 정렬 알고리즘에 대해서 위 링크를 참조했다.