[백준]1197 최소 스패닝 트리(Python)

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

문제 접근

 

우선 최소 스패닝 트리의 개념을 알아야지 문제를 풀 수 있다고 생각해서 개념을 우선 찾아보았다.

하단에 신장 트리의 개념과 크루스칼 알고리즘의 동작 과정을 잘 설명한 사이트를 첨부해놓았다.

 

크루스칼 알고리즘

1. 주어진 모든 간선 정보에 대해 비용이 낮은→높은 순서로 오름차순 정렬

2. 정렬된 간선 정보를 하나씩 확인하며 현재의 간선이 노드들 간의 사이클을 발생시키는지 확인 

=>  부모노드가 같다면 사이클 발생, 같지 않다면 발생x

3. 부모노드가 같다면 최소 신장 트리에 포함x, 다르면 포함

4. 1~3번 과정을 정렬된 모든 간선에 수행 

 

시간 복잡도

간선의 개수가 E개일 때, O(ElogE) => 어디서? 간선을 정렬하는 과정

 

코드

import sys

sys.setrecursionlimit(1000000)  # 재귀 깊이 제한 늘리기
input = sys.stdin.readline

# 찾기 연산(같은 집합에 속하는지 확인)
def find_parent(x):
    if parents[x] != x:
        parents[x] = find_parent(parents[x])
    return parents[x]


# 합집합 연산(두 집합을 합치기 위한 함수)
def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parents[b] = a
    else:
        parents[a] = b

# 정점, 간선 입력
V, E = map(int, input().split())

# 부모 테이블
parents = [i for i in range(V+1)]

# 간선 정보를 담을 리스트와 최소 신장 트리 가중치 변수 선언
edges = []
weight = 0

for _ in range(E):
    s, e, w = map(int, input().split())
    edges.append((w, s, e))

edges.sort()    # 오름차순 정렬

for i in range(E):
    w, s, e = edges[i]

    if find_parent(s) != find_parent(e):
        union_parent(s, e)
        weight += w

print(weight)

 

문제 회고

 

이전에 유니온파인드 알고리즘을 공부했을 때 작성한 find, union 함수를 그대로 가져와서 사용한다는 게 신기했다.

스패닝 트리(신장 트리)가 모든 노드를 포함하면서(연결하면서) 사이클이 존재하지 않아야 한다는 것

최소 스패닝 트리는 위의 개념 + 비용을 최소로 하는 것(오름차순 정렬)

 

 

 

참고

https://techblog-history-younghunjo1.tistory.com/262

[Python] 최소 신장 트리를 찾는 크루스칼(Kruskal) 알고리즘