[백준] #1005 Python

백준 1005번 파이썬

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

아이디어

1. 위상정렬
2. DP

처음에는 위상정렬을 몰랐기 떄문에, 구하고자 하는 노드부터 거꾸로 BFS를 통해 연결된 노드의 max 값을 갱신해 나가면 되겠다고 생각했다. BFS로 풀게 되면 단순히 시간초과 떄문이 아니라 오류가 나는 부분이 있다. 위상정렬과 DP를 사용하면 진입차수의 개수에 따라 문제에 알맞게 순서가 짜여지는데 반해, BFS는 특정 그래프일 때만 알맞은 순서에 배치된다.

위상정렬 알고리즘

노드의 집입차수(노드를 향해오는 간선의 개수), 진출차수(다른 노드를 향해가는 간선의 개수)에 의해 순서가 정해진다.

큐를 이용하는 위상 정렬 알고리즘 동작 과정
1. 진입차수가 0인 모든 노드를 큐에 넣는다
2. 큐가 빌 때까지 다음의 과정을 반복한다

• 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다
• 새롭게 진입차수가 0이 된 노드를 큐에 넣는다

결과 적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다

전체코드

import sys
from collections import deque
 
T=int(sys.stdin.readline())
 
for _ in range(T):
    N,K=map(int,sys.stdin.readline().split())#건물수, 건설순서규칙
    time=[0]+list(map(int,sys.stdin.readline().split()))#건물들의 건설시간
    seq=[[] for _ in range(N+1)]#건설순서규칙
    inDegree=[0 for _ in range(N+1)]#진입차수
    DP=[0 for _ in range(N+1)]#해당 건물까지 걸리는 시간
 
    for _ in range(K):#건설순서규칙 저장
        a,b=map(int,sys.stdin.readline().split())
        seq[a].append(b)
        inDegree[b]+=1
 
    q = deque()
    for i in range(1,N+1):#진입차수 0인거 찾아서 큐에 넣기
        if inDegree[i]==0:
            q.append(i)
            DP[i]=time[i]
 
    while q:
        a=q.popleft()
        for i in seq[a]:
            inDegree[i]-=1#진입차수 줄이고
            DP[i]=max(DP[a]+time[i],DP[i])#DP를 이용해 건설비용 갱신
            if inDegree[i]==0:
                q.append(i)
 
 
    ans=int(sys.stdin.readline())
    print(DP[ans])

참고(공부)한 블로그
https://freedeveloper.tistory.com/390 - 위상정렬 개념
https://developmentdiary.tistory.com/465 - 문제풀이

사실 참고라기 보다는 공부를 했다. 계속 공부해나가다 보면 나도 다른 사람들에게 공부가 되는 블로그를 쓸 수 있겠지!