[백준/Python]1005: ACM Craft

문제

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

 

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

---

풀이

 

2056: 작업 문제와 같은 로직이다.

 

작업이 A → B 순으로 처리되므로 B에 해당되는 작업들의 진입차수를 증가시킨다.
진입차수 정리가 끝났다면 아래의 과정을 거친다.

1. dp 리스트, queue 생성
2. 진입차수가 0인 작업들을 찾음
   • dp값에 해당 작업의 소요시간을 저장
   • queue에 추가
3. 위에서 저장한 queue를 가지고 BFS 실행
   • queue: 지금 당장 시작할 수 있는 작업들
   • queue에서 pop한 작업과 연결된 작업들을 탐색
     • 연결작업의 진입차수를 1 감소시킴
     • 연결작업의 dp값을 갱신함 => max(기존 dp값, 현재 작업의 dp값 + 연결작업의 소요시간)
     • 진입차수가 0이 된 상태라면 queue에 추가
4. 건설해야 할 건물의 dp값 출력

 

전체 코드

# 2056_작업 과 비슷한 문제. DP + BFS를 사용한다.
# 메모리: 37616KB / 시간: 968ms
from sys import stdin
from collections import deque


input = stdin.readline

def bfs():
    dp = [0] * (N+1)
    queue = deque()

    for i in range(1, N+1):
        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
            # 현재 건물을 짓는 최소시간 = 기존값 or 이전 건물을 짓는 최소시간 + 현재 건물을 짓는 시간
            dp[node] = max(dp[node], dp[curr] + time[node])

            if in_degree[node] == 0:
                queue.append(node)
    return dp[W]  # W 건물을 짓는데까지 소요되는 최소 시간


T = int(input())

for _ in range(T):
    N, K = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    in_degree = [0] * (N+1)
    time = [0] + list(map(int, input().split()))  # 건물을 짓는데 걸리는 시간

    for _ in range(K):
        X, Y = map(int, input().split())  # X를 지어야 Y를 지을 수 있음
        graph[X].append(Y)
        in_degree[Y] += 1

    W = int(input())  # 타겟 건물
    print(bfs())