[파이썬] 백준 2056 : 작업 (골드4)

[파이썬] 백준 2056 : 작업 (골드4)

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

---

풀이

방향성 생각

• 위상정렬 + DP. DP라고 하기엔 메모제이션이 크게 중요하지 않아서 위상정렬 위주
• BFS를 사용해서 선행 작업들이 없는 노드에서 시작한다.
• 특정 노드에 필요한 선행 작업들이 모두 충족되면 해당 노드를 큐에 넣는다.
• 큐에 넣을 때는 최대값을 갱신해서 넣어준다.
• 해당 경로를 지나는 값 중 최대값을 넣어야한다.
  

전체코드

from collections import deque
import sys

input = lambda : sys.stdin.readline().rstrip()

N = int(input())
T = [0]*(N+1)
G = [[] for _ in range(N+1)]
pre = [0]*(N+1) # 노드의 선행작업 개수
dp = [0]*(N+1) # 작업 처리 최대시간

Q = deque()
for i in range(1,N+1):
    a,b,*c = map(int, input().split())
    T[i] = a
    pre[i] = b
    for x in c: # 선행작업은 그래프 단방향 연결
        G[x].append(i)
    if not b: # 선행 작업이 없는 경우 바로 큐에 추가
        Q.append(i)

while Q:
    x = Q.popleft()
    for nx in G[x]:
        pre[nx] -= 1
        dp[nx] = max(dp[nx],dp[x]+T[x]) # 기록된 시간, x까지 도달시간 + x실행시간 중 최대
        if pre[nx] == 0: # 전부 처리했으면 큐에 추가
            Q.append(nx)

answer = max([dp[i]+T[i] for i in range(1,N+1)]) # i까지 도달 시간 + i 실행시간 중 최대값
print(answer)

코멘트

• 256MB라서 메모리 널널할줄 알았는데 양방향 간선 모두 넣고 방문정보까지 2D로 만들어버리니까 메모리 초과나서 선행 작업 개수만 카운트 하면서 진행