99클럽 코테 스터디 17일차 TIL + 오늘의 학습 키워드

문제

Baekjoon 2056: 작업

• 설명: 작업들 간의 선행관계가 주어질 때 모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라.

풀이

• A 작업이 B 작업이 선행되어야 한다고 할 때 B -> A 처럼 방향 그래프를 만들어준다.

  • 그래프를 만들어주며 모든 노드의 내차수의 개수를 세준다.

• 선행관계가 없는 노드를 시작으로 탐색하며 방문하는 노드들의 내차수를 1씩 제거해준다.

• 방문할 노드의 내차수가 0이 되는 순간 큐에 넣어준다.

  • 위상정렬을 하는 것이다!

• 하지만 각 작업들은 동시에 수행이 가능하고 선행 작업이 모두 끝나는 시간에 시작이 가능하다.

• 이 점을 처리해주기 위해서 방문할 노드의 내차수가 0이 되는 순간에 우선순위 큐에 그 노드가 끝나는 시간과 같이 넣어준다.

  • 이 우선순위 큐는 노드가 끝나는 시간을 기준으로 정렬한다.
  • 우선순위에서 노드를 꺼내면서 각 노드의 끝나는 시간을 따로 기록해준다.

오늘의 회고

• 문제 1: PriorityQueue 미숙 문제

  • PriorityQueue의 사용이 미숙해 무한반복이 발생해 디버깅을 하여 아래와 같은 인사이트를 얻었다.

  • python의 list, dict, deque 등은 비어있는 경우 False 처럼 인식되어 아래와 같은 상황이 발생한다.

      from collections import deque
      dq = deque()
    
      "YES" if dq else "NO" # No

    • 하지만 from queue import PriorityQueue 같은 경우 주소 값을 반환하기 때문에 항상 양수가 되어 아래와 같은 상황이 발생한다.

      from queue import PriorityQueue
      pq = PriorityQueue()
      
      "YES" if pq else "NO" # YES

  • 때문에 while pq: pq가 비어있든, 비어있지 않든 무한반복이 된다.

• 문제 2: 시작점체크 문제

  • 주어진 문제에서 선행관계는 모든 노드에서 없을 수도 있다. 따라서 기본적으로 시작점은 indegree가 $0$인 노드에서 시작해주어야 한다.
  • 또한 작업이 꼭 마지막 노드에서 끝나리라는 보장이 없다. 마지막 노드만 혼자 선행관계가 없는 경우를 생각해보자. 따라서 가장 큰 끝나는 시간을 출력해주어야한다.

Code

# Baekjoon02056.py
import sys
input = sys.stdin.readline

from queue import PriorityQueue

n = int(input())

cost = [0] * (n + 1) # 노드의 수행 시간
indegree = [0] * (n + 1) # 노드의 내차수
adj_list = [[] for _ in range(n + 1)]
for curr in range(1, n + 1):
    temp = list(map(int, input().split()))

    cost[curr] = temp[0]
    for adj in temp[2:]:
        # 각 노드의 선행작업이 주어지기 때문에 선행작업이 나를 가리키도록 그래프를 만들어준다.
        adj_list[adj].append(curr)
        indegree[curr] += 1

pq = PriorityQueue()

# 내차수가 0인 노드들로부터 시작한다.
for i in range(1, n + 1):
    if indegree[i] == 0:
        pq.put((cost[i], i))

ans = [0] * (n + 1)
while pq.qsize():
    curr_cost, curr = pq.get()
    ans[curr] = curr_cost

    for adj in adj_list[curr]:
        indegree[adj] -= 1

        if indegree[adj] == 0:
            pq.put((curr_cost + cost[adj], adj))

print(max(ans))