[python] 백준 - 11085. 군사 이동

🤔문제 해결

• 크루스칼

1. C에서 출발! 갈 수 있는 곳을 찾아서 우선순위 큐에 넣는다.
2. 우선순위 큐에서 넓이가 가장 넓은 녀석을 뽑는다.
3. 거기서 또 갈 수 있는 곳을 찾아서 큐에 넣는다. (단, 재방문 X)
4. V를 만나면 끝!

노드를 이동하는 동안 최소값을 계속 갱신해준다. (답을 찾아야하므로)

 

💻소스 코드

import sys
from collections import defaultdict
import heapq

input = sys.stdin.readline

P, W = map(int, input().split())  # P개의 지점, W개의 길
C, V = map(int, input().split())  # C 백준수도, V 큐브수도

# 인접노드 만들기
nodes = [input() for _ in range(W)]
adj = defaultdict(list)
for node in nodes:
    a, b, c = map(int, node.split())
    adj[a].append([b, c])
    adj[b].append([a, c])

# 우선순위 큐
visited = [0] * P
pq = []
heapq.heappush(pq, [-1e9, C])
answer = 1e9 # 최소값 찾기

while pq:
    cur_cost, cur_node = heapq.heappop(pq)
    cur_cost *= -1

    if visited[cur_node]:
        continue
    visited[cur_node] = 1

    answer = min(answer, cur_cost)
    if cur_node == V:
        print(answer)
        break

    for next_node, next_cost in adj[cur_node]:
        heapq.heappush(pq, [-next_cost, next_node])

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE