교대최소제곱법
[백준 파이썬 1005번 ACM Craft] 위상정렬 본문
위상정렬이랑 DP를 활용하여 푸는 문제였다
위상정렬로 순서를 정하고 dp를 하는 것보다 위상정렬을 하면서 dp를 계산해나가면 되는 문제
25. 위상 정렬(Topology Sort)
위상 정렬(Topology Sort)은 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 ...
blog.naver.com
위상정렬은 우선순위가 있는 작업들의 순서를 정렬할 때 사용되는 알고리즘이다
DAG Directed Acyclic Graph 유향 비순환 그래프에서만 사용 가능하다 (사이클일 경우 사용 불가)
왜죠?
순환 그래프의 경우 모두 연결되어 있어서 사이클 내에서는 시작점을 찾을 수 없기 때문이다
시간복잡도는 O(V+E) 매우 빠른 편
https://www.acmicpc.net/problem/1005
1005번: ACM Craft
첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부
www.acmicpc.net
import sys
from collections import deque
input = sys.stdin.readline
T = int(input())
for _ in range(T):
N, K = map(int, input().split())
time = list(map(int, input().split()))
graph = [[] for i in range(N+1)]
connect = [0 for i in range(N+1)]
for _ in range(K):
a, b = map(int, input().split())
graph[a].append(b)
connect[b] += 1
goal = int(input())
q = deque()
dp = [0 for _ in range(N+1)]
for i in range(1, N+1):
if connect[i] == 0:
q.append(i)
while q:
start = q.popleft()
dp[start] += time[start-1]
for g in graph[start]:
connect[g] -= 1
dp[g] = max(dp[g], dp[start])
if connect[g] == 0:
q.append(g)
print(dp[goal])
'코딩테스트' 카테고리의 다른 글
[백준 파이썬 14502번 연구소] 구현 최적화 (1) | 2023.10.09 |
---|---|
[백준 파이썬 12015번 가장 긴 증가하는 부분 수열 2] DP, Bisect (0) | 2023.10.05 |
[백준 파이썬 1647번 도시 분할 계획] 튜플과 리스트의 시간 차이 (0) | 2023.09.25 |
[백준 파이썬 1197번 최소 스패닝 트리] 크루스칼 알고리즘, 프림 알고리즘 (0) | 2023.09.24 |
[백준 파이썬 1629번 곱셈] 분할 정복 (0) | 2023.09.12 |