백준 2350번: 대운하

백준 2350번: 대운하

풀이 과정

분명 분리집합 태그로 찾았는데 어째서 MST 문제일까

정답 코드

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


def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    px, py = find(x), find(y)
    if px > py:
        parent[px] = py
    else:
        parent[py] = px

def dfs(x, y):
    Q = list()
    Q.append((x, float('inf')))
    
    V = defaultdict(int)
    V[x] = 1
    
    while Q:
        SN, SD = Q.pop()
        
        if SN == y:
            return SD
        
        for FN, FD in P[SN]:
            if not V[FN]:
                Q.append((FN, min(SD, FD)))
                V[FN] = 1


N, M, K = map(int, input().split())
L = list()
for i in range(M):
    i, j, w = map(int, input().split())
    L.append((w, i, j))
L.sort(reverse = True)
parent = [i for i in range(N + 1)]
P = defaultdict(list)

for c, a, b in L:
    if find(a) == find(b):
        continue
    union(a, b)
    P[a].append((b, c))
    P[b].append((a, c))

R = list()
for k in range(K):
    i, j = map(int, input().split())
    R.append(dfs(i, j))

for r in R:
    print(r)