[백준 1005] ACM Craft ❗

코뉴·2022년 2월 7일

백준🍳

목록 보기

98/149

https://www.acmicpc.net/problem/1005

🥚문제

🥚입력/출력

🍳코드

import sys
from collections import deque
input = sys.stdin.readline


for testcase in range(int(input().strip())):
    """ 입력 """
    # N: 건물의 개수, K: 규칙의 개수
    N, K = map(int, input().split())

    # 건물 건설에 걸리는 시간
    D = [0] + list(map(int, input().split()))

    # rules: 건설 순서 인접 리스트
    # degree: 진입차수 저장
    rules = [[] for _ in range(N+1)]
    degree = [0]*(N+1)
    for _ in range(K):
        first, last = map(int, input().split())
        rules[first].append(last)
        degree[last] += 1

    # W: 건설해야 할 건물의 번호
    W = int(input().strip())
    """ 압력 끝 """

    # dp[i] = 건물 i를 건설하는 데 걸리는 최소 시간
    dp = [0]*(N+1)
    # 큐
    q = deque([])

    # 진입차수가 0인 것을 큐에 삽입
    for i in range(1, N+1):
        if degree[i] == 0:
            q.append(i)
            dp[i] = D[i]

    while q:
        i = q.popleft()
        for j in rules[i]:
            degree[j] -= 1  # 진입 차수를 줄인다
            dp[j] = max(dp[i] + D[j], dp[j])
            # 진입 차수가 0이 되면 큐에 삽입한다
            if degree[j] == 0:
                q.append(j)
    print(dp[W])

🧂아이디어

위상정렬, DP

위상정렬

순서가 정해져 있는 작업을 차례대로 수행해야 할 때 사용하는 알고리즘

방향 그래프의 노드들을 방향성에 거스르지 않게 나열하는 것

진입 차수 (indegree): 어떤 노드로 들어오는 간선의 개수

위상 정렬 알고리즘
1. indegree가 0인 노드를 큐에 삽입
2. 큐가 빌 때까지 아래 과정 반복
- 큐에서 원소를 꺼내고, 그 노드에서 출발하는 간선을 그래프에서 제거 (간선으로 이어져 있던 노드의 indegree가 감소)
- 새롭게 indegree가 0이 된 노드를 큐에 삽입
- 이때, 모든 노드를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것 (위상 정렬 문제에서는 보통 사이클이 발생하는 입력을 주지 않을 것이지만 참고해두기)