[BOJ 1516] 게임 개발

문제

게임 개발

문제 해설

위상 정렬을 이용해 정점들을 모두 검사하여 값을 갱신하는 문제입니다. 왜 위상 정렬을 쓸 수 있냐면 처음 시작점이 어딘지는 모르나, 한 건물을 지어야 다른 건물을 지을 수 있는 구조기 때문에 양방향 그래프가 그려질 수 없고 사이클이 절대로 발생할 수 없기 때문입니다.

위상 정렬을 쓰는 이유는 어떤 건물이 먼저 지어져야 지을 수 있는지 차수 라는 개념을 통해 모든 노드들의 순서를 정렬할 수 있기 때문입니다. 순서만 따라가게 된다면 자동적으로 모든 노드를 방문함과 동시에 상위 건물들을 만족하게 되어 바로 건물을 지을 수 있는 것이죠.

1. 각 노드들의 연결 정보, 노드들의 차수, 각 건물 완성 시간, 총 건물 완성 시간을 저장할 리스트를 만들고 차수가 0인 노드들을 모두 큐에 담습니다.

2. 노드를 하나 꺼내 다음의 단계를 진행합니다.
   2-1. 연결된 하위 노드들의 차수를 하나 뺍니다.(간선 제거)
   2-2. 연결된 하위 노드들의 총 소요 시간과 (하위 노드가 걸리는 시간 + 현 노드의 총 소요 시간) 중 큰 것으로 교체합니다. 왜냐하면 다른 노드가 이미 방문했을 수도 있기 때문입니다.

3. 반복합니다.

풀이 코드

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())
# 연결 정보
connect = [[] for _ in range(n + 1)]
# 정점의 차수
degree = [0] * (n + 1)
# 각 건물 완성 시간
finish = [0] * (n + 1)
# 연결 순서를 담을 큐
q = deque()
# 총 건물 완성 시간
answer = [0] * (n + 1)

for i in range(1, n + 1):
    l = list(map(int, input().split()))
    # 건물 완성 시간 저장
    finish[i] = l[0]
    # 차수 0이면 큐에 저장
    if len(l) == 2:
        q.append(i)
        answer[i] = l[0]
    # 연결 정보 저장
    for x in l[1 : len(l) - 1]:
        connect[x].append(i)
        degree[i] += 1

while q:
    node = q.popleft()
    for next in connect[node]:
        # 상위 노드 소요시간을 하위 노드에 더해주고 다음 노드 큐에 담음
        answer[next] = max(finish[next] + answer[node], answer[next])
        # 차수 -1
        degree[next] -= 1
        # 차수가 0이면 큐에 넣는다
        if degree[next] == 0:
            q.append(next)
for x in answer[1:]:
    print(x)