악곱 == 악성곱슬

위상 정렬, DP

---

이 문제는 선후수 건물 개발 순서가 정해져있다. 이걸 보고 바로 위상정렬이 떠올라야 한다. 문제에서 요구하는 것이 각 건물 개발이 끝나는 시간을 알아내야 한다. 건물 개발은 동시에 이루어질 수 있고, 먼저 지어야 하는 순서대로 지어야 한다. 단순한 위상 정렬 문제로 보이지만, 본래 위상정렬이라는 것은, 출력하는 순서만 정해주는 것이다.

이 문제는 이 순서에 시간이 더해진 응용 문제라고 보면 된다. 아래 사진과 같은 경우를 떠올리며 풀어야 하는 문제이다.

일반 위상정렬이었다면 3 → 4 에서 값이 업데이트 되어 30이라고 출력했을 것이다. 그러나 이 문제는 2번이 완료되는 시간이 1000이기 때문에 실제 정답은 1010이 된다. 이를 적용하기 위해 완료되는 시간을 메모이제이션을 통해서 구해야 한다. 구현한 코드는 아래와 같다.

포인트는 실제 코딩 테스트에서 위와 같은 문제가 출제되었을 때, 테스트케이스에서 예시가 위와 같은 것이 주어지지 않아도 떠올릴 수 있는 능력이라고 생각한다. 이는 많은 경험을 통해 얻어진다고 생각한다.

코드

import sys
from collections import deque

def solution(n):
    que = deque()
    result = [0] * (n + 1)
    for i in range(1, len(in_degree)):
        if in_degree[i] == 0:
            que.append(i)
            result[i] = build_time[i]
    while que:
        cur = que.popleft()
        for nxt in builds[cur]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                que.append(nxt)
            result[nxt] = max(result[cur] + build_time[nxt], result[nxt])
    return "\n".join(map(str, result[1:]))

if __name__ == "__main__":
    N = int(sys.stdin.readline())
    builds = dict()
    build_time = [0] * (N+1)
    in_degree = [0] * (N+1)
    for idx in range(1, N+1):
        builds[idx] = []
    for idx in range(1, N+1):
        tmp = list(map(int, sys.stdin.readline().split()))[:-1]
        build_time[idx] = tmp[0]
        for idx2 in range(1, len(tmp)):
            builds[tmp[idx2]].append(idx)
        in_degree[idx] += len(tmp[1:])
    print(solution(N))