[BOJ/Python] 2056_작업

문제 출처:https://www.acmicpc.net/problem/2056

2056번: 작업

문제

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.

몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)

모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.

입력

첫째 줄에 N이 주어진다.

두 번째 줄부터 N+1번째 줄까지 N개의 줄이 주어진다. 2번째 줄은 1번 작업, 3번째 줄은 2번 작업, ..., N+1번째 줄은 N번 작업을 각각 나타낸다. 각 줄의 처음에는, 해당 작업에 걸리는 시간이 먼저 주어지고, 그 다음에 그 작업에 대해 선행 관계에 있는 작업들의 개수(0 ≤ 개수 ≤ 100)가 주어진다. 그리고 선행 관계에 있는 작업들의 번호가 주어진다.

출력

첫째 줄에 모든 작업을 완료하기 위한 최소 시간을 출력한다.

예제 입력 1

7
5 0
1 1 1
3 1 2
6 1 1
1 2 2 4
8 2 2 4
4 3 3 5 6

예제 출력 1

23

힌트

• 1번 작업 : 0~5 
• 2번 작업 : 5~6
• 3번 작업 : 6~9 
• 4번 작업 : 5~11
• 5번 작업 : 11~12
• 6번 작업 : 11~19
• 7번 작업 : 19~23

---

풀이

 

위상정렬 문제이므로, 다음과 같은 과정을 수행하여 문제를 해결한다.

1. 진입차수(들어오는 간선)가 0인 노드들을 큐에 넣는다.
2. 큐에서 노드를 하나씩 뽑아내고, 해당 노드와 연결되어있는 간선들을 제거한다.
3. 이 과정을 통해 새로 진입차수가 0이 된 노드들을 큐에 넣는다.
4. 2~3의 과정을 큐가 빌 때 까지 반복한다.

예제 1에 대한 풀이는 다음과 같다.

 

• 각 노드들의 연결 상태이다.
• 노드 위에 있는 숫자는 각 노드마다의 수행 시간이다.

 

 

• 선행해야 하는 작업이 있는 경우, 그 작업을 다 마친 이후에 현재 작업을 수행할 수 있다.
• 예를 들어 2번 노드의 경우, 1번 노드의 작업을 수행한 이후에 수행할 수 있으므로 5+1의 시간이 걸린다.
• 표는 최종적으로 해당 노드를 수행하는데 걸리는 시간을 저장할 리스트라고 생각하면 된다.
• 우선 모든 노드에 대하여 0으로 초기화한다.

• 진입차수가 0인 노드를 모두 큐에 넣는다.
• 현재 그래프에서 진입차수가 0인 노드는 1번 노드뿐이다.
• 큐에 있는 원소를 하나 꺼낸다. 역시 현재 큐에 1번 노드뿐이므로 1번 노드를 꺼내고 1번 노드와 연결되어 있는 노드들을 살핀다.
• 1번 노드와 연결되어있는 노드는 2번 노드와 4번 노드가 있다.
• 표를 보면 2번 노드의 경우 5+1로 6으로 갱신되었고, 4번 노드의 경우 5+6으로 11로 갱신되었다.

• 현재 2번 노드와 4번 노드가 진입차수가 0이므로 두 노드를 큐에 넣는다.

• 큐에서 원소를 꺼낸다. 
• 2번 노드가 나왔고, 2번 노드와 연결되어있는 노드들을 살핀다.
• 각 노드들에 대하여 표를 갱신한다.
• 여기서 갱신은 다음과 같은 과정을 통해 진행된다. 예를 들어 3번 노드라면 다음과 같다.
• (표의 3번 노드의 값 = 0)과 (표의 2번 노드의 값 = 6) + (3번 노드의 수행시간 = 3)를 비교하여 더 큰 값으로 갱신한다.
• 5번 노드와 6번 노드의 경우도 동일하다.
• 현재 노드를 큐에 넣기 직전에, (직전 노드의 값) + (현재노드의 수행 시간)으로 하면 되지 않을까라고 생각할 수도 있지만, 위의 예시에서 2번 노드의 수행시간과 4번 노드의 수행시간이 바뀐다면 5번 노드의 경우 수행시간이 더 짧아지는 문제의 조건에 위배되는 경우가 생기게 된다.
• 또한 여기서 3번 노드의 진입차수가 0이 되었으므로 큐에 넣어준다.

• 큐에서 원소를 꺼낸다.
• 4번 노드가 나왔고, 연결되어 있는 노드들의 값을 비교하여 갱신한다.
• 5번 노드와 6번 노드의 진입차수가 0이 되었으므로 큐에 넣어준다.

• 큐에서 원소를 꺼낸다.
• 3번 노드가 나왔고, 연결되어 있는 노드들의 값을 비교하여 갱신한다.

• 큐에서 원소를 꺼낸다.
• 5번 노드가 나왔고, 연결되어있는 노드들의 값을 비교하여 갱신한다.

• 큐에서 원소를 꺼낸다.
• 6번 노드가 나왔고, 연결되어있는 노드들의 값을 비교하여 갱신한다.

• 큐에서 원소를 꺼낸다.
• 7번 노드의 경우 더 이상 연결되어있는게 없다.
• 큐에 더이상 남아있는 원소가 없으므로 종료한다.

• 최종적으로 제일 큰 값이 23이므로, 모든 작업을 수행하려면 23만큼의 시간이 걸리게 된다.

코드는 다음과 같다.

 

import sys
import collections
 
def topological_sort(graph,indegree,result,cost):
    queue = collections.deque()
    for i in range(1,n+1):
        if indegree[i]==0:
            queue.append(i)
            result[i] = cost[i]
 
    while queue:
        node = queue.popleft()
 
        for next in graph[node]:
            indegree[next]-=1
            result[next] = max(result[next],result[node]+cost[next])
 
            if indegree[next]==0:
                queue.append(next)  
 
n = int(sys.stdin.readline())
 
indegree=[0 for _ in range(n+1)]
graph = [[] for _ in range(n+1)]
cost = [0 for _ in range(n+1)]
result = [0 for _ in range(n+1)]
 
for i in range(1,n+1):
    c,num,*nums = map(int,sys.stdin.readline().split())
    indegree[i] = num
    cost[i] = c
    for j in nums:
        graph[j].append(i)
    
topological_sort(graph,indegree,result,cost)
 
print(max(result))