[정글 알고리즘] - [중]-백준 2056 작업 풀이 골드4

문제 링크 : https://www.acmicpc.net/problem/2056

문제 요약

항목	설명
입력	작업 수 N, 각 작업 시간, 선행 작업 개수와 번호
조건	선행 관계가 없는 작업끼리는 동시에 수행 가능
목표	모든 작업을 끝내는 데 필요한 최소 시간 구하기
핵심	위상정렬 + 각 작업의 가장 빠른 완료 시간 계산

문제는 단순히 작업 순서를 하나 구하는 것이 아니라, 모든 작업이 끝나는 최소 시간을 구해야 합니다. 서로 독립인 작업은 동시에 진행할 수 있기 때문에 “순서”만이 아니라 “시간 누적”이 핵심입니다. [Source](https://www.acmicpc.net/problem/2056)

이 문제에서 제일 중요한 감각

1. 위상정렬만으로는 부족하다

위상정렬은 “어떤 순서로 가능한가”를 알려줍니다. 그런데 이 문제는 모든 작업 완료까지 걸리는 최소 시간을 구해야 하므로, 작업 순서만 알아서는 부족합니다.

2. 각 작업의 완료 시간을 기억해야 한다

어떤 작업이 끝나는 가장 빠른 시간을 저장해두고, 그 값을 다음 작업 계산에 계속 사용해야 합니다. 이름은 보통 dp라고 많이 부르지만, 이 글에서는 더 직관적으로 finish_time = 작업 완료 시간 배열이라고 보겠습니다.

3. 선행 작업이 여러 개면 가장 늦게 끝나는 작업을 기다려야 한다

어떤 작업을 시작하려면 선행 작업이 모두 끝나야 하므로, 시작 시점은 선행 작업들 중 가장 늦게 끝나는 작업에 의해 결정됩니다. 그래서 최대값 비교가 필요합니다. [Source](https://www.acmicpc.net/problem/2056)

finish_time이 왜 필요한가?

예시 구조

1번 작업 (3)

↙ ↘

2번 작업 (5) 3번 작업 (4)

↘ ↙

4번 작업 (6)

시간 계산

1번 완료 시간 = 3

2번 완료 시간 = 3 + 5 = 8

3번 완료 시간 = 3 + 4 = 7

4번 완료 시간 = max(8, 7) + 6 = 14

여기서 4번 작업은 2번과 3번이 모두 끝나야 시작할 수 있으므로, 더 빨리 끝난 3번 기준이 아니라 더 늦게 끝난 2번 기준으로 기다려야 합니다.

finish_time[next] = max(finish_time[next], finish_time[now] + work_time[next])

그래프를 어떻게 만들까?

문제에서 “A 작업이 끝나야 B 작업 시작 가능”이라면, 그래프 간선은 A → B로 두어야 합니다.

선행 작업 → 현재 작업

예시

1번을 끝내야 3번 가능 → 1 → 3

2번과 4번이 끝나야 5번 가능 → 2 → 5, 4 → 5

따라서 인접 리스트에는 graph[선행작업].append(현재작업) 형태로 저장해야 합니다.

예제 힌트로 보는 시간 흐름

문제 힌트 시간표

문제 페이지에 제시된 예제 힌트는 아래와 같습니다. [Source](https://www.acmicpc.net/problem/2056)

작업	실행 구간	완료 시간
1번	0 ~ 5	5
2번	5 ~ 6	6
3번	6 ~ 9	9
4번	5 ~ 11	11
5번	11 ~ 12	12
6번	11 ~ 19	19
7번	19 ~ 23	23

왜 마지막 정답이 23인가?

모든 작업은 동시에 시작 가능한 것은 동시에 진행되지만, 결국 전체 작업이 끝나는 시간은 각 작업 완료 시간 중 가장 큰 값이 됩니다.

전체 정답 = max(finish_time)

최종 코드

from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

graph = [[] for _ in range(n + 1)]
indegree = [0] * (n + 1)
work_time = [0] * (n + 1)
finish_time = [0] * (n + 1)

for i in range(1, n + 1):
    data = list(map(int, input().split()))

    work_time[i] = data[0]
    cnt = data[1]

    for j in range(2, 2 + cnt):
        prev = data[j]
        graph[prev].append(i)
        indegree[i] += 1

queue = deque()

for i in range(1, n + 1):
    if indegree[i] == 0:
        queue.append(i)
        finish_time[i] = work_time[i]

while queue:
    now = queue.popleft()

    for next_node in graph[now]:
        finish_time[next_node] = max(finish_time[next_node], finish_time[now] + work_time[next_node])
        indegree[next_node] -= 1

        if indegree[next_node] == 0:
            queue.append(next_node)

print(max(finish_time))

코드 한 줄씩 핵심 설명

코드	설명
graph = [[] for _ in range(n + 1)]	작업 간의 선행 관계를 저장하는 그래프입니다. 선행 작업에서 현재 작업으로 향하는 방향으로 저장합니다.
indegree = [0] * (n + 1)	각 작업이 시작되기 전에 남아 있는 선행 작업 개수를 저장합니다. 위상정렬의 기본 요소입니다.
work_time = [0] * (n + 1)	각 작업 자체에 걸리는 시간을 저장합니다.
finish_time = [0] * (n + 1)	각 작업이 가장 빠르게 끝나는 시간을 저장합니다. 일반적인 풀이에서는 보통 dp라고 부르지만, 여기서는 의미가 드러나도록 완료시간 배열이라고 보면 됩니다.
graph[prev].append(i)	prev 작업이 끝나야 i 작업을 할 수 있다는 뜻입니다. 즉 간선 방향은 prev → i 입니다.
indegree[i] += 1	i 작업의 선행 작업 개수를 하나 늘립니다.
if indegree[i] == 0:	선행 작업이 하나도 없는 작업은 바로 시작할 수 있으므로 큐에 먼저 넣습니다.
finish_time[i] = work_time[i]	바로 시작 가능한 작업은 시작 시간이 0이므로 완료 시간은 자기 작업 시간 그대로입니다.
now = queue.popleft()	현재 처리 가능한 작업 하나를 꺼냅니다.
finish_time[next_node] = max(...)	next_node 작업은 여러 선행 작업이 있을 수 있으므로, 현재까지 알려진 완료 시간과 새로 계산한 완료 시간 중 더 큰 값을 유지해야 합니다. 결국 가장 늦게 끝나는 선행 작업을 기다려야 하기 때문입니다. [Source](https://www.acmicpc.net/problem/2056)
indegree[next_node] -= 1	선행 작업 하나가 처리되었으므로 next_node의 남은 선행 작업 수를 줄입니다.
if indegree[next_node] == 0:	이제 선행 작업이 모두 끝났다면 next_node를 시작할 수 있으므로 큐에 넣습니다.
print(max(finish_time))	전체 작업 완료 시간은 마지막에 끝나는 작업의 완료 시간과 같으므로, 완료시간 배열의 최댓값을 출력하면 됩니다.

자주 틀리는 부분

실수	왜 틀리는가
위상정렬 순서만 구하고 끝냄	이 문제는 순서가 아니라 전체 완료 시간을 구해야 하므로, 완료시간 계산이 반드시 필요합니다.
간선을 반대로 저장함	선행 작업 → 현재 작업으로 저장해야 이후 작업을 제대로 꺼낼 수 있습니다.
finish_time[next] += work_time[next]	선행 작업이 여러 개일 때는 더하는 게 아니라 가장 늦은 선행 작업 기준으로 잡아야 하므로 max가 필요합니다.
진입차수 0 작업의 완료시간 초기화 누락	바로 시작 가능한 작업의 완료시간은 자기 작업 시간으로 먼저 채워야 합니다.

한 번에 정리

이 문제의 핵심 한 문장

위상정렬로 작업 순서를 처리하면서, 각 작업의 가장 빠른 완료 시간을 계속 갱신해야 하고, 선행 작업이 여러 개라면 가장 늦게 끝나는 선행 작업 기준으로 현재 작업 시간이 결정됩니다.

문제는 여러 작업이 선행 관계를 가질 때 모든 작업을 완료하는 최소 시간을 구하는 것입니다. 따라서 단순 위상정렬이 아니라, 위상정렬 과정에서 각 작업의 완료 시간을 함께 계산해야 합니다. [문제 바로가기] [Source](https://www.acmicpc.net/problem/2056)