728x90
https://www.acmicpc.net/problem/1005
1005번: ACM Craft
첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부
www.acmicpc.net
BFS 로 풀다가는 큐와함께 속도 터져나가는 문제입니다. 위상정렬 알고리즘을 통해 큐에 진입되는 조건을 지정해줘야 풀 수 있습니다. 간단하게 설명하자면 특정 노드에서 들어가고 나가는 노드의 수를 기록해 들어가는 노드가 적은 순서로 탐색하는 알고리즘입니다. 특정 노드를 방문하는 조건이 여러 개일 때 사용하는 알고리즘입니다.
from collections import deque
import sys
def solution(N, K, build_times, build_rules, W):
# 인덱스 맞추기
build_times = [0] + build_times
# 위상정렬
topolog_list = [[0, 0] for _ in range(N+1)]
# 트리
tree = [[] for _ in range(N+1)]
# 트리 및 위상정렬 정리
# 트리에는 다음으로 이동 가능한 노드가 들어감
for start, end in build_rules:
tree[start].append(end)
# 위상정렬에는 들어가는 노드와 나오는 노드가 들어감
for i, node in enumerate(tree):
for j, num in enumerate(node):
topolog_list[num][0] += 1
topolog_list[i][1] += 1
# 최대 시간
max_times = [0 for _ in range(N+1)]
# 들어가는 노드가 없는 노드를 큐에 넣음
# 최대 시간도 최신화
queue = deque([])
for idx, (in_node, out_node) in enumerate(topolog_list):
if not in_node and idx:
queue.append(idx)
max_times[idx] = build_times[idx]
while True:
# 큐가 비면 끝
if not queue:
return max_times[W]
# 현재 노드
now_node = queue.popleft()
# 이동 가능한 노드중 들어가는 노드가 하나인 노드로 이동
for node in tree[now_node]:
# 들어가는 노드 하나씩 지우기
topolog_list[node][0] -= 1
# 최대시간과 비교해서 업데이트
if max_times[node] < max_times[now_node] + build_times[node]:
max_times[node] = max_times[now_node] + build_times[node]
# 들어가는 노드가 없으면
if not topolog_list[node][0]:
# 다음 노드가 목적 노드가 아니면 큐에 추가
if node != W:
queue.append(node)
T = int(input())
for _ in range(T):
N, K = map(int, sys.stdin.readline().split())
build_times = list(map(int, sys.stdin.readline().split()))
build_rules = [list(map(int, sys.stdin.readline().split())) for _ in range(K)]
W = int(sys.stdin.readline())
print(solution(N, K, build_times, build_rules, W))
728x90
'Coding Test > BaekJoon_Python' 카테고리의 다른 글
백준 1389 <케빈 베이컨의 6단계 법칙> Python (1) | 2023.11.16 |
---|---|
백준 1007 <벡터 매칭> Python (1) | 2023.11.15 |
백준 1753 <최단경로> Python (1) | 2023.11.14 |
백준 1238 <파티> Python (1) | 2023.11.14 |
백준 1753 <최단경로> Python (1) | 2023.11.14 |