문제
서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다.
이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다.
위의 예시를 보자.
이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번건물의 건설을 시작할수 있다.
따라서 4번건물의 건설을 완료하기 위해서는 우선 처음 1번 건물을 건설하는데 10초가 소요된다. 그리고 2번 건물과 3번 건물을 동시에 건설하기 시작하면 2번은 1초뒤에 건설이 완료되지만 아직 3번 건물이 완료되지 않았으므로 4번 건물을 건설할 수 없다. 3번 건물이 완성되고 나면 그때 4번 건물을 지을수 있으므로 4번 건물이 완성되기까지는 총 120초가 소요된다.
프로게이머 최백준은 애인과의 데이트 비용을 마련하기 위해 서강대학교배 ACM크래프트 대회에 참가했다! 최백준은 화려한 컨트롤 실력을 가지고 있기 때문에 모든 경기에서 특정 건물만 짓는다면 무조건 게임에서 이길 수 있다. 그러나 매 게임마다 특정건물을 짓기 위한 순서가 달라지므로 최백준은 좌절하고 있었다. 백준이를 위해 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성해주자.
해설
특이하게도 그래프와 DP 이론을 동시에 사용하여야 풀 수 있는 조금 까다로운 문제다. 거기에 덧붙여서 위상정렬에 대한 개념을 알고 있어야 문제를 풀 수 있었다.
문제 설명이 다소 복잡하긴 하지만 결국 접근법은 아래와 같다.
- 가장 먼저 지어야 하는 건물을 찾는다.
- 그 건물부터 '차례대로' 건물을 지어나간다
- 건물에 대한 DP 리스트를 만들어, 지금 건물을 짓기까지 필요했던 '건설 시간'을 누적해 저장한다.
근데 여기서 문제가 발생한다.
어느 건물부터 지어야 할 지 '순서'를 알아야 차례대로 DP 값을 구할 수 있다는 것이다.
이 순서는 위상정렬(TopologicalSort)을 통해 구할 수 있다.
위상정렬에 대한 내용은 자료가 많이 나와있으니 따로 검색해보기를 권장하지만, 간단히만 이야기하자면
1) 그래프에서 '들어오는 간선'이 없는 노드를 찾아 큐에 넣는다.
2) 큐에서 노드를 꺼내 해당 노드와 해당 노드에 연결된 간선을 모두 제거한다. 제거한 노드를 결과에 추가한다.
3) 이후 그래프에서 다시 '들어오는 간선'이 없는 노드를 찾아 큐에 넣는다.
4) 1~3 을 반복한다.
위상 순서를 알았다면, DP 값을 순서에 따라 차례대로 구해나가면 된다.
DP 값은 그림을 보았다면 이해할 수 있겠지만, 다음과 같다.
DP[i] = i번 건물을 짓기 위해 필요한 이전 건물들 중 DP 최댓값 + i번 건물의 건설시간
코드
from collections import deque
def TopologicalSort(PrereqTech):
result = []
# 들어오는 간선이 없는 노드를 큐에 추가
Q = deque()
visisted = [False] * (N+1)
while True:
for i in range(1, N+1):
if not PrereqTech[i] and not visisted[i]:
visisted[i] = True
Q.append(i)
if Q:
node = Q.popleft()
result.append(node)
for i in range(1, N+1):
if node in PrereqTech[i]:
PrereqTech[i].remove(node)
continue
break
return result
T = int(input())
for i in range(T):
N, K = map(int, input().split()) # 건물, 규칙순서
builds = list(map(int, input().split())) # 건물 당 걸리는 건물 건설시간
builds.insert(0, 0)
techTree = [[] for _ in range(N+1)]
PrereqTech = [[] for _ in range(N+1)] # i번째 건물 건설에 필요한 선행건물 목록
for j in range(K):
first, second = map(int, input().split())
techTree[first].append(second)
PrereqTech[second].append(first)
W = int(input()) # 승리하기 위해 지어야 하는 건물 번호
nodes = TopologicalSort(PrereqTech[:]) # 위상 정렬
DP = builds[:]
for node in nodes:
for next in techTree[node]:
if DP[next] < DP[node] + builds[next]:
DP[next] = DP[node] + builds[next]
print(DP[W])참고자료
https://leetcode.com/discuss/general-discussion/1078072/introduction-to-topological-sort
Introduction to Topological Sort - LeetCode Discuss
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com