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이 된 노드를 큐에 삽입
  • 이때, 모든 노드를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것 (위상 정렬 문제에서는 보통 사이클이 발생하는 입력을 주지 않을 것이지만 참고해두기)

• 위상 정렬 알고리즘의 시간 복잡도
  • O(V+E) : 모든 노드를 확인하며 그 노드에서 출발하는 간선을 제거해야 함. 모든 노드와 간선을 확인함.

문제 풀이 아이디어

• 건물 i 건설에 걸리는 최소 시간은

• 직전 단계(건물 i의 차수 - 1)에 지어야 하는 건물 j, k, l, ... 등을 짓는 데 걸리는 시간의 최대값 + 건물 i를 짓는데 걸리는 시간

• 위상 정렬 알고리즘을 이용하여 위 값을 갱신해 줄 수 있다.

참고: https://velog.io/@enchantee/%EB%B0%B1%EC%A4%80-1005-Python-kvth6jbu