[Python] 1516 - 게임개발 (골드3)

1. 문제 설명

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

1516번: 게임 개발

 

---

2. 아이디어

이 때 처음 위상 정렬에 대해서 접했었는데 재밌는 알고리즘이었다.

위상 정렬에 대해서 간단히 설명하자면 정점 정보를 얻고 싶으면 선행 조건을 만족해야 한다는 것이다.

 

값을 입력받을 때, 선행 조건으로 충족되어야 하는 부모 노드와 숫자를 체크한다.

숫자가 0이라면 선행 조건이 없다는 뜻이므로 큐에 삽입해놓았다가 정점 정보가 다 만들어지면

큐에서 값을 하나씩 빼가며 time을 체크하고 해당 건물을 선행조건으로 가지는 자식 노드를 탐색한다.

있다면 자식 노드의 선행 조건이 하나 충족되었다는 의미로 값을 1씩 내리다가 0이 되면 자식을 큐에 넣는다.

 

글로만 적으니 헷갈리는데 간단히 정리하자면 각각의 배열은 다음과 같은 기능을 한다.

• 정점 간의 연결 정보를 담은 2차원 배열 (값을 수정하면 안 됨)
• 만족하는 조건이 몇 개 남았는지 알려주는 1차원 배열 (조건이 만족되면 해당 건물 인덱스의 값을 1씩 내림)
• 각 건물의 건설 소모 시간 정보

 

예시로 문제에서 제공하는 테스트 케이스를 받았을 때, 가장 처음 큐에 담긴 정점은 1이므로

흐름대로 따라가보자.

 

그러면 간선 정보가 담긴 그래프를 행과 열에 대해 읽어줘야 한다. 이게 무슨 소리인가?

열에 대한 정보는 현재 나를 선행조건으로 가지는 자식 노드를 의미한다.

여기서 걸리는 정점의 남은 선행 조건 수를 1씩 내려주기 위해 필요하다.

그렇다면 행에 대한 정보는 무엇일까? 바로 건설 소모 시간 누적을 위함이다.

 

위의 과정에서 2가 큐에 삽입되었으므로, 사이클을 한 바퀴 돌려보자.

2를 선행조건으로 갖는 정점은 아무것도 없으므로 그냥 지나가면 된다.

그런데 우리가 원하는 결과는 "2가 지어지는데 결국 얼마나 걸렸는가? "이므로 1의 시간값을 2에 더해줘야 한다.

즉, 여기서 행에 대한 정보는 곧 해당 건물을 짓기까지 걸렸던 소요 시간의 누적값이며,

선행 조건이 여러개였다면 그 중에서 가장 뒤늦게 지어진(값이 가장 큰) 부모 노드의 시간 정보를 더해주면 된다.

 

---

3. 코드

import sys
from collections import deque

input = sys.stdin.readline

def solution():
    n = int(input())
    parent = [[0]*(n+1) for i in range(n+1)]
    is_valid = [0]*(n+1)
    time = [0]*(n+1) 
    queue = deque()

    for idx in range(1, n+1):
        _input = list(map(int, input().split()))
        time[idx] = _input[0]
        for value in _input[1:-1]:
            if value != -1:
                parent[idx][value] = 1
                is_valid[idx] += 1
        if is_valid[idx] == 0: # 따로 선행 조건이 없다면 큐에 삽입
            queue.append(idx)

    while queue:
        building = queue.popleft()
        tmp = 0
        for idx in range(1, n+1):
            if parent[idx][building] == 1: # 해당 건물을 선행조건으로 갖는 건물 탐색
                #parent[idx][building] = 0 => 선행 건물의 시간을 못 끌고 옴,,건드리면 ㄴㄴ
                is_valid[idx] -= 1
                if is_valid[idx] == 0:
                    queue.append(idx)
            
            if parent[building][idx] == 1: # 0으로 안 바뀌었으면 선행 건물의 시간 가져오기
                tmp = max(time[idx], tmp)
        time[building] += tmp

    for i in time[1:]:
        print(i)

solution()