백준 1197 최소 스패닝 트리

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

그래프가 주어젔을때 최소 스패닝 트리의 가중치의 합을 구하는 문제이다.

일단 스패닝 트리 자체를 처음 접한 개념이어서 문제를 풀지 못하고 답을 찾아보고 풀었고, 그래서 내용을 정리 한다.

스패닝 트리

그래프(혹은 트리) 안에 정점(vertex)와 각각의 정점을 이어주는 간선(edge)가 있으면, 해당 트리 중 모든 정점을 포함하는 최소 연결 트리이다. 풀어서 말하면 1) 모든 정점은 간선으로 연결되어 있고, 2) 각 간선들이 사이클을 생성하지 않아 최소치를 갖는 서브 트리로 이해 하면 될것 같다.

두번째, 세번째 트리는 첫번째 트리의 스패닝 트리이다. 이와 같이 모든 정점이 연결되어 있고 최소 간선 조건을 만족하기 위해 사이클을 만들지 않는 서브 트리들을 스패닝 트리라고 이해하면 될것 같다.

스패닝 트리의 특징

트리의 정점의 수가 n 개 있다고 하면 스패닝 트리의 간선의 개수는 모든 정점이 최소 개수의 간선으로 연결되어야 하기 때문에 n-1개이다.

최소 스패닝 트리(MST)

스패닝 트리 중 간선들의 가중치 합이 최소가 되는 트리가 최소 스패닝 트리이다.

Kruskal 알고리즘

일종의 greedy 알고리즘 중 하나로 매 순간에 최소 가중치를 갖는 간선을 선택하고 해당 간선을 통해 노드들이 연결되면 트리가 사이클을 생성하는지 파악하고, 사이클을 생성하지 않는다면 추가하는 방식
1. 최소 가중치 부터 선택을 시도하기 위해 간선들을 가중치 기준으로 오름차순 정렬 한다.
2. 정렬된 간선 정보를 앞에서부터 하나씩 선택
3. 선택된 간선을 연결 했을떄 사이클을 생성하는지 파악
4. 사이클을 생성하면 pass
5. 사이클을 생성하지 않으면 트리에 추가
6. 추가된 연결정보 갱신

• 위 알고리즘에서 간선 정보가 사이클을 생성하는지 파악하기 위해서 union-find 알고리즘을 사용
• greedy 알고리즘들은 매순간에 최선의 선택이 최선의 결과를 만든다는 개념으로 알고 있고, 이는 항상 최선의 답을 도출한다는 보장은 없다. 하지만 최소 스피닝 트리에 한해서는 greedy 알고리즘 중 하나인 Kruskal 알고리즘은 최선의 답을 도출한다고 한다.

union-find 알고리즘

원 정의는 이해가 되지 않아서, 이해한것을 정리하자면 다음과 같다.
그래프가 있고 해당 그래프에 새로운 노드가 추가될때 마다 추가되는 노드의 부모 정보를 그래프의 루트 노드로 변경해 한 그래프는 모두 같은 루트 노드 정보를 갖게 만든다.

위와 같은 노드들을 연결해서 그래프를 만들때 union-find 알고리즘을 사용한다고 생각해보자.

우선 1번 노드와 2번 노드를 연결해 1-2 그래프와 3번 노드와 4번 노드를 연결해 4-5 그래프를 만들면 다음과 같이 1-2 그래프의 루트 정보로 1을 3-4번 그래프의 루트 노드 정보로 3을 저장한다.

위 같은 상황에서 2번 노드와 3번 노드를 연결 한다고 하면 unio-find 알고리즘에 따라 1-2-3-4 그래프의 루트 노드는 다음과 같이 1번이 된다.

2번 노드와 3번 노드가 연결될때 3번 노드의 루트를 2번 노드의 루트로 변경한다.

위와 같이 그래프가 이어질때, 그러니까 union 작업을 할때 루트를 정하는 규칙을 정해야 하는데, 연결된 노드중 가장 작은 노드 번호 혹은 가장 큰 번호가 루트 노드가 된다.

위 작업을 재귀적으로 구현 하기 위해서 그래프끼리 합쳐질때 루트 노드 번호를 갱신하는 union함수와 union 작업을 진행 할때 루트 노드를 찾을 필요가 있어 find 함수를 구현하였고, 구현된 코드는 다음과 같다.

parent = [i for i in range(v)]  # 노드의 수 만큼 생성하고 처음에는 각 노드의 루트 노드가 본인이 되도록 초기화

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


def union(x, y):
    root_x = find(x)
    root_y = find(y)
    parent[root_y] = root_x
    return root_x

해당 코드에서 parent 리스트는 각 노드들의 루트 노드 정보를 담고 있는 리스트이고 각각의 노드들이 연결되지 않아 그래프를 생성하고 있지 않기 때문에 자신의 번호로 초기화 한다.

풀이 코드

위의 두가지 알고리즘을 통해 구현한 전체 코드는 다음과 같다.

import sys

v, e = map(int, sys.stdin.readline().split())

lines = []
for _ in range(e):
    lines.append(list(map(int, sys.stdin.readline().split())))

lines.sort(key=lambda x: x[2])  # 가중치 값 기준 오름차순 정렬
min_cost = 0
parent = [i for i in range(v)]


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


def union(x, y):
    root_x = find(x)
    root_y = find(y)
    parent[root_y] = root_x
    return root_x


for i in range(e):
    start, end, weight = lines[i]
    if find(start - 1) != find(end - 1):  # 루프를 만들지 않는다
        if start < end:
            union(start - 1, end - 1)
        else:
            union(end - 1, start - 1)
        min_cost += weight
    else:  # 루프를 만든다
        pass

print(min_cost)