[백준/파이썬] 1005 : ACM Craft

문제 : https://www.acmicpc.net/problem/1005

1005번: ACM Craft

문제 요약 : 각 건물의 건설시간과 선후관계가 주어졌을 때, 특정 건물을 짓는 최단 시간을 구한다.

 

오랜만에 백준을 푸려니 개념이 가물가물했다..... 제대로 공부하지 않았다는거겠지

눈물을 뒤로 하고 이론부터 정리하고 간다,,, 다음엔 DP문제 시간 단축한다 즌쯔.....

 

 

 

※ 아직 공부하는 과정에 있어 틀린 말이 많을 수 있음...

 

---

1. 위상정렬(Topology Sort)

위상정렬은 순서가 정해져 있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다.

 

가장 쉽게 이해할 수 있는 예시는 라면 끓이는 작업이다.

라면을 끓이는 방법 중 가장 큰 논쟁은 수프 먼저냐, 면 먼저냐 같은 것이다.

그러나 수프와 면을 넣기 전 물을 넣어야한다는 것은 논쟁의 여지가 없다.

 

즉, 작업i 와 작업j 사이에 간선(i,j)가 존재한다면 작업i는 반드시 작업j보다 먼저 수행된다. 이 성질만 만족한다면 어떤 순서라도 상관없다. 이런 성질을 만족하는 정렬을 위상정렬이라고 한다.

 

또한 위상정렬은 사이클이 발생하지 않는 방향그래프 DAG(Directed Acyclic GrapH)에만 적용이 가능하다.

 

 

1) 큐를 이용한 방식

① 진입차수가 0인 정점을 큐에 삽입

② 큐에 들어있는 정점을 뺀 후, 연결된 간선 제거

③ 제거 이후 진입차수가 0인 정점을 큐에 삽입

④ 큐가 빌 때까지 반복

 

모든 정점을 방문하기 전에 큐가 빈다면 사이클이 존재한다는 뜻

모든 정점을 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과

 

 

2) 스택을 이용한 방식

① 그래프에서 방문하지 않은 노드면 DFS를 수행(시작하는 정점의 순서는 무관)

② DFS가 끝나면 해당 노드를 스택에 추가

③ 스택에서 역순으로 출력하면 위상 정렬의 결과

 

 

2. 메모이제이션(Memoization)

동일한 연산을 반복해야 할 때 이전에 연산한 값을 메모리에 미리 저장해 둠으로써 계산의 반복수행을 제거하여 프로그램 실행 속도를 향상시키는 기술

DP(동적 계획법)에서 사용되는 방법

 

출처 :

쉽게 배우는 알고리즘 개정판

https://yjs03057.tistory.com/4

https://hongjw1938.tistory.com/35

 

---

풀이 )

위상 정렬의 방법 중 큐를 이용한 방법

나중에 시간이 되면 스택을 이용한 방법도 풀어볼까 싶다 지금은 녹초...

 

parentsNum: 진입차수의 개수

relation[i]: i번째 이후 지을 수 있는 건물들의 번호

 

처음에는 parentsNum을 만들 생각을 못하고 그냥 X,Y를 거꾸로 저장해서 relation에 parents들을 저장했는데, 그러면 진입차수가 0인 정점의 간선을 지울 때 parents들을 하나하나 돌면서 찾아야해서 잘못된 접근인 것을 알았다.

 

parentsNum이 0인 정점들에 dp값을 넣어주고 q에 저장한다.q에 저장된 정점을 popleft하여 연결된 정점들의 dp값을 갱신해준다.연결된 정점들의 parentsNum이 0이면 q에 추가해준다.

이를 목표값W의 parentsNum이 0이될때까지 반복해준다.

from collections import deque
import sys
input = sys.stdin.readline

for _ in range(int(input())):   # T동안 반복
    N, K = map(int,input().split()) # 건물의 개수와 건물간 규칙개수
    buildTime = [0] + list(map(int,input().split()))
    relation = [[] for _ in range(N+1)]
    parentsNum = [-1] + [0]*(N)
    
    for _ in range(K):
        X, Y = map(int,input().split()) # X를 거쳐야 Y가 됨
        relation[X].append(Y) 
        parentsNum[Y] += 1
        
    W = int(input())
    dp = [0]*(N+1)
    q = deque()
    
    for i in range(1,N+1):  # 진입차수가 0인 정점 찾기
        if parentsNum[i] == 0:  # 여러개일수 있으니까 break안함
            q.append(i)
            dp[i] = buildTime[i]
            
    while q :# DP 메모이제이션
        node = q.popleft()
        for nextNode in relation[node]:
            parentsNum[nextNode] -= 1
            dp[nextNode] = max(dp[nextNode], dp[node]+buildTime[nextNode])
            if parentsNum[nextNode] == 0:
                q.append(nextNode)
        if parentsNum[W] == 0:
            print(dp[W])
            break

성공~~ 시간과 메모리를 단축하는 방법은 조금 더 능숙해지면 찾아보는 걸로,,