[백준] [파이썬] [위상정렬] [DP] 2056번: 작업

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

2056번: 작업 문제보기

 

제한시간: 2초
메모리 제한: 256 MB

문제

수행해야 할 작업 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

---

입력받는게 까다롭고 헷갈리다. 그것만 잘 해결하면 1005번: ACM Craft 문제와 비슷하다.

위상정렬이나 그래프 문제는 그림을 그려보는게 최고이다.

 

 

 

위 그림처럼 진입할때 가장 큰 걸리는 시간을 선택하며 저장해주어야한다. 따라서 각 작업 노드에 들어오는 진입차수 간선의 값을 골라 자신의 걸린 값을 더해주면 되겠다. 이걸 DP를 이용해서 기록해두자. 

 

arr: 진입차수(언급수) 기록 

arr = [0,0,1,1,1,2,2,3]으로

1은 0번, 2는 1번, 3은 1번, 4는 1번, 5는 2번, 6은 2번, 7은 3번 연결된다

 

graph: 각 index별로 연결된 노드 번호를 넣는다

graph = [[],[2,4],[3,5,6], [7], [5,6], [7], [7], []]

1번 노드가 2,4번 노드랑 연결되어 있고 

2번 노드가 3,5,6번 노드로 가고 

3번 노드가 7번 노드로 

4번 노드가 5,6번 노드로 

5번 노드가 7번 노드로 

6번 노드가7번 노드로 간다 

7번 노드에서 가는 노드는 없다 

 

time은 각 index에서 수행 시간을 기록한다 

[0,5,1,3,6,1,8,4]로 

1번 노드는 5시간, 2번 노드는 1시간, .... 걸린다 

 

---

정답 코드

import sys 
from collections import deque

sys.stdin=open('input.txt','r')

# sys.setrecursionlimit(10000)

input=sys.stdin.readline


if __name__=="__main__":
    N=int(input())
    graph=[[] for _ in range(N+1)]
    dp=[0]*(N+1)                    # 각 작업까지 수행하는데 걸린 시간 기록
    arr=[0]*(N+1)                   # 진입차수 기록
    time=[0]                        # 각 작업당 수행 시간 
    for i in range(1,N+1):
        # i작업 수행 시간, 먼저 완료되어야 할 작업 수, 먼저 완료되어야 할 작업
        info=list(map(int, input().split()))    
        time.append(info[0])
        if info[1]!=0:              # 먼저 완료되어야 할 작업이 있으면
            for j in info[2:]:
                graph[j].append(i)  # 먼저 완료되어야 할 작업에 현재 작업 append
                arr[i]+=1           # 현재 작업 진입차수 상승
    
    Q=deque()
    # 작업들을 순서대로 확인하면서 우선순위 작업을 먼저 큐에 넣고 작업까지 수행하는데 걸린 시간 기록 dp에 자체 수행시간을 넣는다
    for i in range(1,N+1):
        if arr[i]==0:               # 먼저 완료되어야 할 작업이 없는 i작업. 즉, 우선순위
            Q.append(i)
            dp[i]=time[i]
    
    while Q:
        x=Q.popleft()
        for e in graph[x]:
            arr[e]-=1               # x관련 작업 e의 작업 수 차등 
            dp[e]=max(dp[x]+time[e], dp[e]) # 현재 작업까지 걸린시간+다음 작업수행 시간 vs 다음 작업까지 걸리는 시간
            if arr[e]==0:           # 작업 수행이 완료되면 큐에 넣음 
                Q.append(e)
    
    print(max(dp))

 

---