[백준/Python]2056: 작업

문제

https://www.acmicpc.net/problem/2056
백준 문제집 - 0x1A강 - 위상 정렬

 

알고리즘: 다이나믹 프로그래밍, 방향 비순환 그래프, 위상 정렬

---

풀이

 

🗝️ DP + 위상정렬 문제다.

각 작업은 선행 작업이 끝난 이후부터 시작할 수 있고, 서로 선행관계가 없는 작업들은 병렬적으로 작업할 수 있다.
즉, 현재 작업의 선행 작업들 중 가장 늦게끝나는 작업을 시작 기준으로 삼아야한다.

 

일단 A: 선행작업, B: 후 작업 일 때 A → B 형태로 진입차수를 정리해준다.
그리고 DP 리스트를 생성 후, 진입차수가 0인 작업들을 찾는다.
해당 작업들의 DP값을 주어진 작업시간값으로 갱신 후, 작업번호를 queue에 삽입한다.
BFS를 실행하며 DP값들을 갱신시켜준다. 과정은 아래와 같다.

1. queue에서 노드를 꺼냄
2. 꺼낸 노드(A)의 다음 작업들(B)을 하나씩 탐색한다.
   • 진입차수를 1 감소시켜줌
   • DP[B]의 값을 갱신함
     • (기존 DP값), (A의 DP값 + B의 작업시간) 중 더 큰 값을 선택
   • 진입차수가 0이 된다면 queue에 작업(B) 삽입

 

아래 예제 1 데이터로 진행 과정을 살펴보자.

7
5 0
1 1 1
3 1 2
6 1 1
1 2 2 4
8 2 2 4
4 3 3 5 6

선행 관계를 정리하면,

1 = []        # 1번 작업은 선행 작업 없음
2 = [1]       # 2번 작업은 1번 작업이 끝난 후 시작 가능
3 = [2]       # 3번 작업은 2번 작업이 끝난 후 시작 가능
4 = [1]       # 4번 작업은 1번 작업이 끝난 후 시작 가능
5 = [2, 4]    # 5번 작업은 2번, 4번이 끝난 후 시작 가능
6 = [2, 4]    # 6번 작업은 2번, 4번이 끝난 후 시작 가능
7 = [3, 5, 6] # 7번 작업은 3, 5, 6이 끝난 후 시작 가능

이렇게 된다.

 

DP 갱신 과정은 다음과 같다.

👉 1번 작업이 끝난 후 - 2, 4번 작업 시작 가능

dp[2] = dp[1] + time[2] = 5 + 1 = 6
dp[4] = dp[1] + time[4] = 5 + 6 = 11

👉 2번 작업이 끝난 후 - 3, 5, 6번 작업 시작 가능

dp[3] = max(dp[3], dp[2] + time[3]) = max(0, 6 + 3) = 9
dp[5] = max(dp[5], dp[2] + time[5]) = max(0, 6 + 1) = 7
dp[6] = max(dp[6], dp[2] + time[6]) = max(0, 6 + 8) = 14

👉 4번 작업이 끝난 후 - 5, 6번 작업시간 갱신 가능

dp[5] = max(dp[5], dp[4] + time[5]) = max(7, 11 + 1) = 12
dp[6] = max(dp[6], dp[4] + time[6]) = max(14, 11 + 8) = 19

👉 5, 6, 3번 작업이 끝난 후 - 7번 작업 시작 가능

dp[7] = max(dp[7], dp[3] + time[7]) = max(0, 9 + 4) = 13
dp[7] = max(dp[7], dp[5] + time[7]) = max(13, 12 + 4) = 16
dp[7] = max(dp[7], dp[6] + time[7]) = max(16, 19 + 4) = 23

 

전체 코드

# ⭐ DP + BFS 문제
# 메모리: 39632KB / 시간: 332ms
from sys import stdin
from collections import deque


input = stdin.readline

N = int(input())
graph = [[] for _ in range(N+1)]
in_degree = [0] * (N+1)
time = [0] * (N+1)  # 각 작업들의 소요시간

for i in range(1, N+1):
    t, m, *nodes = map(int, input().split())

    time[i] = t
    if m != 0:
        in_degree[i] += m  # 현재 노드의 진입차수 기록

        for node in nodes:
            graph[node].append(i)  # 선행노드 -> 현재노드로 연결될 수 있게 저장


def bfs() -> int:
    queue = deque()
    dp = [0] * (N+1)  # dp[x] = x작업까지 마치는데에 걸리는 최대 소요시간

    for i in range(1, N+1):
        # 진입차수가 0인 작업들을 큐에 넣어주고 dp 업데이트
        if in_degree[i] == 0:
            queue.append(i)
            dp[i] = time[i]

    while queue:
        curr = queue.popleft()

        for node in graph[curr]:
            in_degree[node] -= 1

            # 선행작업 후 현재작업을 수행하는데에 걸리는 시간
            # 이전 선행작업 중 가장 많이 소요되는 작업이 끝난 후에 현재 작업을 시작할 수 있음.
            dp[node] = max(dp[node], dp[curr] + time[node])

            if in_degree[node] == 0:
                queue.append(node)
    return max(dp)


print(bfs())

DP 문제는 풀어도 풀어도 헷갈리고... 어렵다 아직 ㅎㅎㅎ