작업 [백준 2056] - python

import heapq
import sys
input = sys.stdin.readline
INF = 1e6 + 1

def BOJ2056() :
  N = int(input())
  time = [0]
  graph = [[] for _ in range(N+1)]
  indegree = [0 for _ in range(N+1)]
  queue = []
  
  for i in range(N) :
    temp = list(map(int, input().split()))
    time.append(temp[0])
    
    if len(temp) > 2 :
      indegree[i+1] = len(temp[2:])
      for k in temp[2:] :
        graph[k].append(i+1)

  for i in range(1, N+1) :
    if indegree[i] == 0 :
      heapq.heappush(queue, (time[i], [i, time[i]]))
  
  result = 0
  
  while queue :
    _, [curr, curr_time] = heapq.heappop(queue)
    result = max(result, curr_time)
    for i in graph[curr] :
      indegree[i] -= 1 
      if indegree[i] == 0 :
        next_time = curr_time + time[i]
        heapq.heappush(queue, (next_time, [i, next_time]))
  print(result)

BOJ2056()

 

접근 방법 :

1. 위상정렬을 적용 하였다. 적용 근거는 작업 수행전에 선행되어야 하는 작업이 있기 때문에 적용하였다.

2. 우선순위 큐를 적용한 이유는 모든 작업을 완료하기 위한 최소 시간을 알기 위함이다. 

문제의 조건에서 선행관계가 없는 작업들은 동시에 진행될 수 있다.

선행조건이 완료된 먼저 끝낼 수 있는 작업들은 먼저 해치우는 것이 관건이라 생각했다.

 

우선순위 큐를 사용하지 않으면 다음과 같은 경우가 생길수 있다.

1번은 6의 시간이 필요,

2번은 3의 시간이 필요 

 

1번과 2번은 3번 작업의 선행조건이다.

작업시간에 우선순위 큐를 사용하지 않으면 큐의 탐색 순서에 따라 

2번의 작업을 3의 시간을 소모해서 완료한 후에 3의 시간을 가지고 3번의 작업을 큐에 넣을수 있다.

하지만 정답은 1번과 2번이 완전히 소모된 6의 시간을 3의 작업을 시작할때 가지고 있어야 한다.

 

장애물 이였던 것 :

접근방법의 2번 내용을 떠올리기 어려웠던 것 같다.

 

 

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

2056번: 작업