[백준] 1516번 게임 개발 (feat. 위상 정렬, 다이나믹 프로그래밍)

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

 

문제 분석

• 첫 번째 단계(문제 요약 및 조건 파악)

- 문제 요약
특정 건물을 짓기 전에 선행되어야 하는 건물이 존재.
모든 건물을 짓는데 걸리는 최소의 시간을 구해라.

- 입력
첫째 줄에 건물의 종류 수 N(1 <= N <= 500)
다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어짐. (번호는 1~N) 각 줄은 -1로 끝남.
ex)
5
10 -1 -> 1번 건물 짓는데 걸리는 시간 10, 선수 건물 없음.
10 1 -1 -> 2번 건물 짓는데 걸리는 시간 10, 선수 건물 1번 건물.
.
.
.

- 출력
N개의 각 건물이 완성되기까지 걸리는 최소시간 출력 할 것.

 

• 두 번째 단계(문제 핵심 파악)

전형적인 위상정렬 문제로 판단된다.(선수 과목 문제와 비슷)
그런데, 출력조건을 잘 살펴보자.
N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력해야한다.

N개의 각 건물이 완성되는 시간에 대해서 생각해보자.

처음에 진입차수가 0인 건물은 건축 소요시간이 처음 주어진 개별적인 건축 소요시간과 동일 할 것이다.

그렇다면, 먼저 지어져야 지을 수 있는 건물의 건축 시간에 대해 생각해보자. 즉 초기에 진입차수가 0이 아닌 건물들에 대해서 생각해보자는 의미다.
만약 3번 건물의 개별적인 건축 소요시간은 5이고, 1번 건물의 소요시간은 1이고, 3번건물을 짓기 위해서는 1번 건물이 먼저 지어져야 한다고 가정해보자.
그러면, 3번 건물의 총 건축 소요시간은 5 + 1로 총 6이 걸릴 것이다.

그런데 만약에 추가조건으로 2번 건물의 소요시간은 2이고, 3번 건물을 짓기 위해서는 1번 건물과 2번건물이 먼저 지어져야 한다고 가정하면 어떨까?
3번 건물의 총 건축 소요시간은 5 + 1인 6이 아니라 5 + 2인 7이 될 것이다.
왜냐하면 3번 건물을 짓기위해서는 1번건물과 2번건물이 선행되어야하는데,
1번 건물이 1이 걸려서 완공되어도 2번건물은 완공까지 1의 시간이 더 필요하기 때문이다.

즉, 1번과 2번 건물이 선행되어야 하는 3번 건물의 착공까지는 1번과 2번 건물 중 소요시간이 더 많은 건물의 소요시간만큼이 필요한셈이다.

즉, 여러개의 노드와 연결된 x노드의 총 소요시간 = 연결된 노드중 소요시간이 가장 큰 노드의 소요시간 + x 노드의 소요 시간이다

이 로직은 다이나믹 프로그래밍으로 구성할 수 있다.

result[node] = max(result[node], result[now] + build_time[node])

 

코드 작성

 

'''
- 문제 요약
특정 건물을 짓기 전에 선행되어야 하는 건물이 존재.
모든 건물을 짓는데 걸리는 최소의 시간을 구해라.

- 입력
첫째 줄에 건물의 종류 수 N(1 <= N <= 500)
다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어짐. (번호는 1~N) 각 줄은 -1로 끝남.
ex)
5
10 -1 -> 1번 건물 짓는데 걸리는 시간 10, 선수 건물 없음.
10 1 -1 -> 2번 건물 짓는데 걸리는 시간 10, 선수 건물 1번 건물.
.
.
.

- 출력
N개의 각 건물이 완성되기까지 걸리는 최소시간 출력 할 것.

i)
전형적인 위상정렬 문제로 판단된다.(선수 과목 문제와 비슷)
그런데, 출력조건을 잘 살펴보자.
N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력해야한다.

N개의 각 건물이 완성되는 시간에 대해서 생각해보자.

처음에 진입차수가 0인 건물은 건축 소요시간이 처음 주어진 개별적인 건축 소요시간과 동일 할 것이다.

그렇다면, 먼저 지어져야 지을 수 있는 건물의 건축 시간에 대해 생각해보자. 즉 초기에 진입차수가 0이 아닌 건물들에 대해서 생각해보자는 의미다.
만약 3번 건물의 개별적인 건축 소요시간은 5이고, 1번 건물의 소요시간은 1이고, 3번건물을 짓기 위해서는 1번 건물이 먼저 지어져야 한다고 가정해보자.
그러면, 3번 건물의 총 건축 소요시간은 5 + 1로 총 6이 걸릴 것이다.

그런데 만약에 추가조건으로 2번 건물의 소요시간은 2이고, 3번 건물을 짓기 위해서는 1번 건물과 2번건물이 먼저 지어져야 한다고 가정하면 어떨까?
3번 건물의 총 건축 소요시간은 5 + 1인 6이 아니라 5 + 2인 7이 될 것이다.
왜냐하면 3번 건물을 짓기위해서는 1번건물과 2번건물이 선행되어야하는데,
1번 건물이 1이 걸려서 완공되어도 2번건물은 완공까지 1의 시간이 더 필요하기 때문이다.

즉, 1번과 2번 건물이 선행되어야 하는 3번 건물의 착공까지는 1번과 2번 건물 중 소요시간이 더 많은 건물의 소요시간만큼이 필요한셈이다.

즉, 여러개의 노드와 연결된 x노드의 총 소요시간 = 연결된 노드중 소요시간이 가장 큰 노드의 소요시간 + x 노드의 소요 시간이다.


'''

# 건물의 종류 수 N
import sys
from collections import deque

n = int(input())

# 건물들의 관계를 입력받고 저장할 리스트
graph = [[] for i in range(n + 1)]

# 진입차수를 저장할 리스트
indegree = [0 for i in range(n + 1)]

# 각 건물들을 건축하는데 걸리는 시간을 저장할 리스트
build_time = [0 for i in range(n + 1)]



# 각 건물의 건축 소요 시간과 선수 관계를 입력받고 저장
for i in range(1, n + 1):
    # 입력 받은 데이터를 임시로 저장할 리스트
    tmp = list(map(int, sys.stdin.readline().rstrip().split()))
    build_time[i] = tmp[0]  # 각 건물들의 건축 소요시간 저장
    for j in tmp[1:]:
        if j != -1:
            graph[j].append(i)
            indegree[i] = indegree[i] + 1

# # 위상 정렬 함수
def topology_sort():
    result = [0 for i in range(n + 1)] # 큐에서 꺼낸 노드 번호에 해당하는 건물을 짓는데 걸리는 시간을 저장
    q = deque() # 큐 선언

    # 처음 시작 할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, n + 1):
        if indegree[i] == 0:
            q.append(i)
            result[i] = build_time[i]   # 처음에 진입 차수가 0인 건물은 건축 소요시간은 처음 주어진 개별적인 건축 소요시간과 동일.

    # 큐가 빌 때까지 반복
    while q:
        now = q.popleft()
        for node in graph[now]:
            indegree[node] = indegree[node] - 1 # now와 연결된 노드들의 진입차수 -1 해줌.
            # 한 건물이 여러 건물을 지어야 지을 수 있는 경우, 그 건물들 중 제일 오래 걸리는 건물이 지어지고 나서 지어야 하므로
            result[node] = max(result[node], result[now] + build_time[node])
            if indegree[node] == 0:
                q.append(node)
    for i in range(1, len(result)):
        print(result[i])

topology_sort()

※ 이 문제는 위상정렬 + 다이나믹 프로그래밍 문제이다.
기본적으로 위상정렬 문제인데, 
"한 건물이 여러 건물을 지어야 지을 수 있는 경우, 그 건물들 중 제일 오래 걸리는 건물이 지어지고나서 지을 수 있다는 것" 이것을 DP로 잘 풀어서 적용하는 것이 핵심. DP 적용 위치도 잘 고민해야함.