[Python] BOJ 1516번 - 게임 개발

1. 링크

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

2. 난이도(solved.ac 참고)

골드3

3. 풀이

	# https://www.acmicpc.net/problem/1516
	import sys
	from collections import deque
	q = deque()
	n = int(input())
	indegree = [0] * (n+1)
	times = [0] * (n+1)
	dp = [0] * (n+1)
	graph = [[] for _ in range(n+1)]
	for i in range(1, n+1):
	tower = list(map(int, input().split()))
	times[i] = tower[0]
	if len(tower) > 2:
	for j in tower[1:-1]:
	graph[j].append(i)
	indegree[i] += 1
	for i in range(1, n+1):
	if indegree[i] == 0:
	q.append(i)
	dp[i] = times[i]
	while q:
	now = q.popleft()
	for i in graph[now]:
	indegree[i] -= 1
	dp[i] = max(dp[i], dp[now] + times[i])
	if indegree[i] == 0:
	q.append(i)
	for i in dp:
	if i != 0:
	print(i)

view raw 게임개발.py hosted with ❤ by GitHub

이 문제는 위상정렬을 이용한 동적계획법 문제이다.

위상정렬의 알고리즘은 다른 곳에 이미 잘 나와있으므로 짧게 얘기하면 아래와 같은 방식이다.

1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
  1) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
  2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

tower 배열의 마지막 값은 늘 -1이며 이것은 신경쓸 필요가 없으므로 그 이전 부분까지만 고려한다. tower의 첫번째 값은 해당 인덱스 번째 건물의 완성 시간을 나타내며 두번째 값부터 -1 전까지의 값의 개수만큼 진입차수를 갖고, graph 배열에 넣는다.

시작부터 진입차수가 0이라면 바로 소요시간 배열 times의 값을 최종 결과값인 dp에 우선 박고 큐에 넣은 뒤, 하나씩 빼고 그 큐에 달려있는 그래프들을 순차적으로 돌면서 now 위치를 통해 오는 것과 dp 자체의 값 중 더 큰 값으로 업데이트를 해준다.