백준 #1197 최소 스패닝 트리 (파이썬) : 크루스칼 알고리즘

Yongjun Park·2022년 6월 25일
0

문제집: 단기간 성장

목록 보기
18/19

오늘의 한 마디
드디어 최소 스패닝 트리를 배웠다.

문제

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

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

입력

첫째 줄에 정점의 개수 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보다 작거나 같은 데이터만 입력으로 주어진다.

출력

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

예제 입력 1

3 3
1 2 1
2 3 2
1 3 3

예제 출력 1

3

발상

스패닝 트리 = 신장 트리

필자가 과거에 작성한 트리의 정의 내용에 따르면, 트리란 사이클이 없이 모든 정점이 연결되어있는 그래프다. 사이클이 없는 그래프이므로 정점의 개수가 V개이면 간선의 개수는 V-1개이다.

스패닝 트리는 트리의 정의와 크게 다를게 없다.
다만, 어떤 그래프의 부분 그래프를 지칭한다는 점에서 차이가 있다.

어떤 그래프(트리가 아니어도 됨)가 있고,
그 그래프의 모든 정점을 지나는 트리를 만들면, 그게 바로 스패닝 트리다.

Stack Overflow 글에 좋은 예시가 하나 있어서 가져와봤다.

위 사진에서 세번째에 나온 그래프는, 트리이긴 하지만 스패닝 트리는 아닌 예시다.

최소 스패닝 트리(Minimum Spanning Tree; MST)

Graph에서 만들 수 있는 스패닝 트리의 예시가 두번째, 세번째에 나와 있다.

Graph에는 각 간선의 가중치가 주어져 있으며, 따라서 스패닝 트리 별로 가중치의 합 역시 얻을 수 있다.

최소 스패닝 트리는, 스패닝 트리의 가중치 합을 최소로 하는 스패닝 트리를 의미한다.
당연히 유일하다는 보장은 하지 못한다.

최소 스패닝 트리를 어디에다 쓰는지는...
백준 알고리즘 분류 - 최소 스패닝 트리 문제들을 참고하기 바란다.

크루스칼 알고리즘(Kruskal Algorithm)

최소 스패닝 트리를 구하는 방법은 다양하지만,
가장 대중적인 것이 바로 이번에 소개할 크루스칼 알고리즘이다.

이 링크에 시각화가 매우 잘 되어 있으니, 한번 보시길 추천한다.

알고리즘의 동작 과정을 설명하자면 다음과 같다.

  1. 모든 간선을 가중치 오름차순으로 정렬한다.
  2. 가중치가 가장 낮은 간선부터 순회하면서,
  3. 이 간선이 추가된다면 사이클을 발생시키는지 확인한다.
    1. 사이클을 발생시킨다면, continue
    2. 사이클을 발생시키지 않는다면 추가한다.

그렇게 모든 간선을 돌고 나면, 추가된 간선들이 바로 최소 신장 트리다.

사이클을 발생시키는지 확인하는 방법?

사이클이라고 하니까, 필자가 과거에 풀었던 문제 중에 백준 1956. 운동이라는 문제가 떠올랐다.

위 문제에서는 플로이드-워셜을 사용할 때 arr[i][i] 요소를 0이 아닌 INF로 초기화한 채 3중 for문을 돌리면 arr[i][i]에 (사이클이 발생할 경우) 사이클의 최소 가중치가 들어가 있는 방식으로 문제를 해결했다.

하지만 위 문제에서 정점은 400개 이하로 매우 적었고, 양수 가중치만 주어졌기 때문에 플로이드-워셜을 사용했던 것이다.


이번 최소 스패닝 트리 문제는 정점도 많고, 가중치가 음수가 될 수 있을 뿐 아니라, 근본적으로 스패닝 트리를 만드는 과정에서 간선이 바뀔 수 있기 때문에 플로이드-워셜로 푸는 것은 매우 부적절하다.

그 대신, 매우 직관적인 방법인 Union-Find를 활용한다.

n, m = map(int, sys.stdin.readline().rstrip().split())

parent = [i for i in range(n+1)]

def get_parent(x):
    if parent[x] == x:
        return x
    parent[x] = get_parent(parent[x]) # get_parent 거슬러 올라가면서 parent[x] 값도 갱신
    return parent[x]

def union_parent(a, b):
    a = get_parent(a)
    b = get_parent(b)

    if a < b: # 작은 쪽이 부모가 된다. (한 집합 관계라서 부모가 따로 있는 건 아님)
        parent[b] = a
    else:
        parent[a] = b        

def same_parent(a, b):
    return get_parent(a) == get_parent(b)

이 알고리즘을 그대로 가져다 쓴다.
아래 풀이를 보면 매우 쉽게 이해할 수 있을 것이다.


풀이

import sys
input = lambda: sys.stdin.readline().rstrip()

V, E = map(int, input().split())

# Kruskal Algorithm
# https://techblog-history-younghunjo1.tistory.com/262
edges = []
for _ in range(E):
    A, B, C = map(int, input().split())
    edges.append((A, B, C))
edges.sort(key=lambda x: x[2]) # C(Cost)가 적은 것부터 정렬


# Union-Find
parent = [i for i in range(V+1)]

def get_parent(x):
    if parent[x] == x:
        return x
    parent[x] = get_parent(parent[x]) # get_parent 거슬러 올라가면서 parent[x] 값도 갱신
    return parent[x]

def union_parent(a, b):
    a = get_parent(a)
    b = get_parent(b)

    if a < b: # 작은 쪽이 부모가 된다. (한 집합 관계라서 부모가 따로 있는 건 아님)
        parent[b] = a
    else:
        parent[a] = b        

def same_parent(a, b):
    return get_parent(a) == get_parent(b)


answer = 0
for a, b, cost in edges:
    # cost가 작은 edge부터 하나씩 추가해가면서 같은 부모를 공유하지 않을 때(사이클 없을 때)만 확정
    if not same_parent(a, b):
        union_parent(a, b)
        answer += cost
print(answer)
profile
추상화되었던 기술을 밑단까지 이해했을 때의 쾌감을 잊지 못합니다

0개의 댓글