문제
문제
수행해야 할 작업 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
풀이
❓어떻게 풀까?
- 각 작업에 대한 소요 시간, 선행작업, 후행작업 리스트를 저장한다.
# 인덱스 0은 비워두고 1부터 채웠다. # 각 작업의 소요 시간 cost = [0, 5, 1, 3, 6, 1, 8, 4] # 각 작업의 선행 작업 pre = [[], [], [1], [2], [1], [2, 4], [2, 4], [3, 5, 6]] # 각 작업의 후행 작업 adj = [[], [2, 4], [3, 5, 6], [7], [5, 6], [7], [7], []]
- 각 작업이 완료되었는 지 여부, 시작 시간과 끝 시간을 저장하는 리스트를 초기화한다.
# 얘네도 마찬가지로 인덱스 0은 쓰지 않는다. working_at: [[0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0]] checked: [False, False, False, False, False, False, False, False]
- BFS를 위한 덱을 선언하고, 처음에 시작할 수 있는 작업(즉, 선행 작업이 없는 작업)을 덱에 집어넣는다.
# 선행작업이 없는 작업을 덱에 넣는다 q = deque([[1, 0]]) # 1은 작업 번호, 0은 작업의 시작 시간
- BFS 시작, 왼쪽 요소를 빼 작업을 완료하고, 후행 작업을 덱에 넣는다.
task1) checked = [False, True, False, False, False, False, False, False] working_at = [[0, 0], [0, 5], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0]] q = deque([[2, 5], [4, 5]]) task2) checked = [False, True, True, False, False, False, False, False] working_at = [[0, 0], [0, 5], [5, 6], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0]] q = deque([[4, 5], [3, 6]]) task4) checked = [False, True, True, False, True, False, False, False] working_at = [[0, 0], [0, 5], [5, 6], [0, 0], [5, 11], [0, 0], [0, 0], [0, 0]] q = deque([[3, 6], [5, 11], [6, 11]]) task3) checked = [False, True, True, True, True, False, False, False] working_at = [[0, 0], [0, 5], [5, 6], [6, 9], [5, 11], [0, 0], [0, 0], [0, 0]] q = deque([[5, 11], [6, 11]]) task5) checked = [False, True, True, True, True, True, False, False] working_at = [[0, 0], [0, 5], [5, 6], [6, 9], [5, 11], [11, 12], [0, 0], [0, 0]] q = deque([[6, 11]]) task6) checked = [False, True, True, True, True, True, True, False] working_at = [[0, 0], [0, 5], [5, 6], [6, 9], [5, 11], [11, 12], [11, 19], [0, 0]] q = deque([[7, 19]]) task7) checked = [False, True, True, True, True, True, True, True] working_at = [[0, 0], [0, 5], [5, 6], [6, 9], [5, 11], [11, 12], [11, 19], [19, 23]] q = deque([])
- 항상 마지막 인덱스의 작업이 가장 늦게 끝나는 건 아니므로, 끝나는 시간이 가장 늦은 시간을 답으로 프린트한다.
23
⌨️ 코드로 짜볼까?
1️⃣ 입력 받기
n = int(input())
# 해당 작업의 소요 시간 리스트
cost = [0]
# 해당 작업의 선행 작업들 이중 리스트
pre = [[] for _ in range(n+1)]
# 해당 작업의 후행 작업들 이중 리스트
adj = [[] for _ in range(n+1)]
# cost, pre, adj 채우기
for number in range(1, n+1):
line = list(map(int, input().split())) # [4, 3, 3, 5, 6]
cost.append(line.pop(0)) # cost = [4]
for i in range(line.pop(0)): # for i in range(3)
adj[line[0]].append(number) # adj[3].append(number) # 5, 6도 받음
pre[number].append(line.pop(0)) # pre[number].append(3) # 5, 6도 받음2️⃣ checked 리스트, working_at 리스트 초기화
# 해당 작업이 끝났는 지를 저장하는 리스트
checked = [False]*(n+1)
# 해당 작업의 시작과 끝 시간을 저장하는 이중 리스트
working_at = [[0, 0] for _ in range(n+1)]3️⃣ BFS를 위한 덱 초기화
# BFS를 위한 덱 선언 ([작업 번호, 해당 작업 시작 시간])
q = deque()
# 처음 시작할 수 있는 작업이 여러 개 일 수 있기 때문에, 선행작업이 없는 작업을 몽땅 집어넣음
for i in range(1, n+1):
if not pre[i]:
q.append([i, 0])4️⃣ BFS
# BFS
while q:
# 하나 꺼내
task, time = q.popleft()
# 해당 task의 시작시간과 끝나는 시간 설정
working_at[task][0] = time
working_at[task][1] = time + cost[task]
# checked True로 변경
checked[task] = True
# non-checked이면서 가능한 작업 덱에 집어넣음
for a in adj[task]: # 후행 작업 a의
for t in pre[a]: # 선행 작업 t가
if not checked[t]: # 완료되지 않았다면
break # 실행할 수 없으므로 종료 (덱에 추가하지 않음)
else: # break가 안걸렸다면 = 모든 선행 작업 t가 완료되었다면
if not checked[a]: # 동시에 a가 완료되지 않은 작업이라면
max_time = -1
for b in pre[a]: # a의 선행작업 중 가장 느린 종료시간을 시작시간으로 갖는다.
max_time = max(max_time, working_at[b][1])
q.append([a, max_time]) # 덱에 추가5️⃣ 정답 출력
# 항상 마지막 인덱스가 마지막에 끝나진 않기 때문에, 가장 늦은 종료 시각이 답
ans = -1
for w in working_at:
ans = max(ans, w[1])
print(ans)소스코드
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
# cost, pre, adj 초기화
cost = [0]
pre = [[] for _ in range(n+1)]
adj = [[] for _ in range(n+1)]
# 입력 받기
for number in range(1, n+1):
line = list(map(int, input().split()))
cost.append(line.pop(0))
for i in range(line.pop(0)):
adj[line[0]].append(number)
pre[number].append(line.pop(0))
checked = [False]*(n+1)
working_at = [[0, 0] for _ in range(n+1)]
# 덱 초기화
q = deque()
for i in range(1, n+1):
if not pre[i]:
q.append([i, 0])
# BFS
while q:
task, time = q.popleft()
# 해당 task의 시작시간과 끝나는 시간 설정
working_at[task][0] = time
working_at[task][1] = time + cost[task]
# checked True로 변경
checked[task] = True
# non-checked이면서 가능한 작업 덱에 집어넣음
for a in adj[task]:
for t in pre[a]:
if not checked[t]:
break
else:
if not checked[a]:
# 선행 작업의 끝나는 시간 중 최댓값 계산
max_time = -1
for b in pre[a]:
max_time = max(max_time, working_at[b][1])
q.append([a, max_time])
# 정답 출력
ans = -1
for w in working_at:
ans = max(ans, w[1])
print(ans)폼 미쳤다
어흥🦁