🔴 문제 개요
🚀 난이도 : GOLD 3
세준이가 세준크래프트를 만든다고 합니다. N개의 건물을 짓는데 걸리는 최소 시간을 구하고 싶다고 하는데요, 각 건물을 짓기 위해서는 필요한 선수 건물들이 존재합니다.
문제 유형
건물을 짓기 위해서 선수로 지어야하는 건물을 고려해야 하니, 위상 정렬 알고리즘을 고려해볼 수 있을 것 같습니다. 기본적인 위상정렬 알고리즘으로 구해낼 수 있는 건물을 짓는 순서에 더해, 각 건물을 짓는데 필요한 최소 시간까지 고려해야 하니 조금 더 생각을 해봐야 할 것 같습니다.
🟠 Solution
먼저 위상 정렬 알고리즘을 수행하기 위해 정의한 입력부 부터 보도록 하겠습니다.
import sys
from collections import deque
input = sys.stdin.readline
N = int(input().rstrip())
# init
htbd = [0 for _ in range(N + 1)] # have to before done : 선수 건물 개수
ttb = [0 for _ in range(N + 1)] # time to build : 해당 건물을 짓는데 드는 시간
adj = [[] for _ in range(N + 1)] # 다음 지을 수 있는 건물들
builded = [0 for _ in range(N + 1)] # 최종 시간을 담을 리스트위상정렬 알고리즘은 선수 노드가 없는 노드부터 처리해가는 알고리즘입니다. 이를 위해 선수 건물의 개수를 관리할 자료구조(htbd)과, 해당 노드가 선수 노드인 다른 노드를 관리할 자료구조(adj)가 필요합니다. 또한, 건물을 짓는 데 필요한 시간(ttb)까지 주어지게 됩니다.
주어지는 실제 input에 따라 그래프를 연결해보겠습니다.
# 그래프 연결, 선수 건물 개수 파악
for i in range(1, N + 1):
row = list(map(int, input().rstrip().split()))
for idx, r in enumerate(row):
if idx == 0:
ttb[i] = r
continue
if r == -1:
break
adj[r].append(i)
htbd[i] += 1여기서 중요한 점은 이후 실제 노드 처리 과정에서 활용하기 위해 htbd와 adj를 잘 구분해서 입력 받아야겠죠. 입력 형식이 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어지는 형식으로 입력되기 때문에, 위상 정렬 알고리즘의 개념이 잘 정립되어있지 않다면 제가 그랬던 것 처럼 살짝 헷갈릴 수 있는 부분이기 때문에 굳이 구분했습니다.
문제에서 주어진 예제 1번에 대해 그래프를 그려보면 아래와 같은 느낌입니다. 빨간색 숫자는 해당 건물을 짓는데 필요한 시간입니다. 그림에 따르면 adj[1]은 [2, 3, 4]를 원소로 가져야 합니다.
다음은 선수 노드가 없는 노드들을 우선 큐에 삽입합니다.
# 먼저 지을 수 있는 건물들 큐에 삽입
for i in range(1, N + 1):
if htbd[i] == 0:
queue.append(i)이제 노드를 처리해보겠습니다.
while queue:
node = queue.popleft()
builded[node] += ttb[node]
for nxt_v in adj[node]:
htbd[nxt_v] -= 1
# 선수 건물들 중 가장 나중에 지어지는 건물의 시간으로 갱신
builded[nxt_v] = max(builded[nxt_v], builded[node])
if htbd[nxt_v] == 0:
queue.append(nxt_v)
print("\n".join(map(str, builded[1:])))기본적인 구조는 일반적인 위상 정렬 알고리즘의 구조와 같습니다. 큐에서 node를 꺼내고, 그 node와 연결되어있는 다른 노드의 선행 노드 개수를 1 줄여줍니다. 이 때 선행 노드 개수가 0이 된 노드들을 큐에 넣어서 이후에 처리하는 방식입니다.
- 이제 문제의 핵심인 건물을 짓는데 걸리는 시간을 처리하는 방법입니다. 특정 건물(노드)는 선행 건물이 여럿 있을 수 있습니다. 그렇기 때문에, 해당 건물이 지어지기 위해서는 여러 선행 건물 중 가장 마지막에 지어진 선행 건물 이후에 지어질 수 있겠죠.
- 그래서 큐에서 꺼내 처리하기 전 특정 선행 건물이 큐에서 꺼내서 처리될 때, 해당 건물과 연결된 후행 건물의 시간을 가장 나중에 지어지는 건물의 시간으로 갱신해줍니다.
builded[nxt_v] = max(builded[nxt_v], builded[node])- 이 과정이 dynamic programming 방식이기도 하기 때문에, 문제 유형에 dp도 포함되어있는 것 같습니다.
- 이제 그 후행 건물을 큐에서 꺼내 처리할 때, 해당 건물을 짓는데 걸리는 시간(
ttb[node])을 더해주면 됩니다.
마지막으로 개행 문자를 전 후로 각 건물을 짓는데 필요한 시간을 이어 붙여 출력해주면 됩니다.
🟡 후기
위상정렬 알고리즘의 개념을 머릿속에서 다시 한 번 명확하게 정리하게 해준 고마운 문제였습니다. dp 방법론까지 적용시켜볼 수 있었던 좋은 문제였다고 생각합니다.
🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!
