[알고리즘] BOJ 1197 최소 스패닝 트리 #Python

[BOJ] 1197 최소 스패닝 트리 바로가기

📍 문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

---

📍 입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

---

📍 출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

---

📍 풀이

🧷 풀이 과정

📒 Kruskal 알고리즘의 정확한 정보는 요기!

간선의 가중치가 존재하는 최소 스패닝 트리를 구해야 하는 경우는 Kruskal MST 알고리즘을 적용해야 한다.
Kruskal MST 알고리즘은 아래의 순서에 따라 수행된다.

1. 주어진 간선을 가중치를 기준으로 오름차순으로 정렬한 후 가중치가 작은 간선부터 차례로 연결한다.
2. 간선 연결 중 싸이클이 발생한다면 즉, 이미 정점들끼리 연결되어 있어서 새로운 간선을 연결할 필요가 없는 경우에 해당 간선은 연결에서 제외한다.

📒 Union & Find의 정확한 정보는 요기!

해당 정점들을 연결할 간선을 추가할 때 싸이클이 발생을 확인하기 위해서 Union & Find 알고리즘을 이용한다.

✍ 코드

# BOJ 1197 최소 스패닝 트리
# https://www.acmicpc.net/problem/1197

from sys import stdin

def solution(V, edges):

    answer = 0

    # Union & Find
    parent = [i for i in range(V+1)]
    def find(x):
        if x != parent[x]:
            parent[x] = find(parent[x])
        return parent[x]
    def union(x,y):
        x = find(x)
        y = find(y)
        parent[max(x,y)] = parent[min(x,y)]

    # 가중치(x[2])를 기준으로 오름차순으로 정렬
    edges.sort(key = lambda x : x[2])

    for s, e, w in edges:
        # 싸이클이 생기지 않으면
        if find(s) != find(e):
            # 해당 간선 연결
            union(s,e)
            # 해당 간선의 가중치 누적합
            answer += w

    return answer

# input
V, E = map(int,stdin.readline().split())
edges = [list(map(int,stdin.readline().split())) for _ in range(E)]

# response
res = solution(V, edges)
print(res)