BaekJoon 9372번 : 상근이의 여행 (python)

BaekJoon 9372번 : 상근이의 여행 (S4 60.783%)

상근이의 여행 문제

크루스칼 알고리즘(Kruskal Algorithm)을 이용한 최소 신장 트리(MST) 문제이다.

• 이전에 풀었던 유니온 파인드와 비슷한 코드지만 서로 다른 목적을 가진 알고리즘인 크루스칼 알고리즘을 사용한다. 크루스칼 알고리즘은 가중치가 있는 무방향 그래프에서 모든 노드를 최소한의 비용으로 연결하는 부분 그래프(트리)를 찾는데 사용된다.
• 기본적으로 간선의 정보를 입력받고 가중치가 가장 낮은 순서대로 정렬을 한 다음 루트 노드가 갖지 않으면 union을 통해 합쳐주는 방식을 이용한다.
• 유니온 파인드 알고리즘과는 다르게 union에서 높이를 신경쓰지 않고 합쳐주기만 하면 된다.

import sys
input = sys.stdin.readline

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

def union(x,y) :
    newx = find(x)
    newy = find(y)

    if newx > newy :
        root[newy] = newx
    else :
        root[newx] = newy

T = int(input())

for _ in range(T) :
    N, M = map(int,input().split())
    root = list(i for i in range(N+1))
    edge = list()
    result = 0
    for i in range(M) :
        a, b = map(int,input().split())
        edge.append((a,b))
    edge.sort()
    for i in edge :
        a, b = i[0], i[1]
        if find(a) != find(b) :
            union(a,b)
            result += 1
    print(result)