[BOJ 1516] 게임 개발 (Python)

풀이

이 문제는 위상 정렬을 이용하여 푸는 문제이다. 저는 위상 정렬에 대해 몰랐었기에 개념을 공부한 후 풀었는데 위상 정렬 기본 코드를 옆에 놓고 보면서 구현하느라 시간이 은근 걸린 문제였다. 위상 정렬 구현 코드의 원리를 이해했다면 어느정도 쉽게 풀 수 있는 문제라고 생각했다. (온전히 본인의 생각이다.)

문제의 포인트는 현재 건물을 짓기 위한 최소 시간을 구할 때 먼저 지어야하는 건물 여러개가 있다고 가정하자. 이때 먼저 지어야하는 건물들 중 최고로 많이 걸리는 시간을 더해주어야 한다. 코드에서는 result[b] = max(result[b], result[now]) 부분이다.
--> 예시를 들어 이유를 설명하겠다.

(Ex) 1번 건물을 짓기 위해서는 선수 건물로 2번, 3번 건물을 건설해야 한다. 2번 건물은 4초가 걸리고, 3번 건물은 10초가 걸린다고 하자. 그러면 1번 건물은 4초 후에 지을 수 있는 것이 아닌 10초 후에 1번 건물을 지을 수 있다. 4초 후에 2번 건물을 짓고나서 1번 건물을 지으려고 할 때 3번 건물은 아직 지어지지 않았기 때문에 1번 건물을 지을 수 없다.

해당 포인트를 이해하면 문제를 풀 수 있다고 생각한다.

코드

import sys
from collections import deque

input = sys.stdin.readline
N = int(input())

# 노드와 간선의 정보 저장한다고 생각하면 됨
building = [[] for _ in range(N + 1)]
# 각 노드의 진입차수 저장
indegree = [0] * (N + 1)
# 건물 짓는데 걸리는 시간
cost = [0] * (N + 1)

for i in range(1, N + 1):
    data = list(map(int, input().split()))[:-1]
    cost[i] = data[0]
    building_data = data[1:]

    # 간선 연결 및 진입차수 설정
    for j in building_data:
        building[j].append(i)
        indegree[i] += 1


# 위상 정렬 함수
def topology_sort():
    result = [0] * (N + 1)
    q = deque()

    for i in range(1, N + 1):
        if indegree[i] == 0:
            q.append(i)

    while q:
        now = q.popleft()
        # 큐에서 꺼낸 노드 번호에 해당하는 건물을 짓는데 걸리는 시간 저장
        # 선수 건물 짓는데 걸리는 시간이 포함되어 있음!
        # 즉, '선수 건물 짓는데 걸리는 시간 + 현재 건물 짓는데 걸리는 시간'이 저장됨
        result[now] += cost[now]
        for b in building[now]:
            indegree[b] -= 1
            # b번호 건물을 짓기 전에 먼저 지어야하는 선수 건물 짓는데 걸리는 시간으로 갱신
            result[b] = max(result[b], result[now])
            if indegree[b] == 0:
                q.append(b)

    return result


answer = topology_sort()
for i in range(1, N + 1):
    print(answer[i])