https://acmicpc.net/problem/1647

풀이

최소 스패닝 트리를 구하는 방법 중 하나인 크루스칼 알고리즘을 사용하여 해결하였다.
최종적으로 최소 스패닝 트리가 형성되기 때문에(사이클이 발생하지 않고, 최소 가중치 합으로 연결되어 있다) 그 최소 스패닝 트리를 구성하는 간선들 중에 가중치가 가장 큰 간선을 빼주어 마을을 2개로 분리시킨다.

최소 스패닝 트리

스패닝 트리(신장트리)

무방향 그래프에서 사이클을 포함하지 않으며 모든 정점이 트리에 포함되어 있는 부분 그래프를 스패닝 트리라고 한다. 스패닝 트리는 여러 형태로 존재할 수 있으며, 특징은 n개의 정점을 갖는 경우 신장 트리에 속하는 간선의 수는 n-1개이며, 사이클을 이루지 않는다는 점이다.

최소 스패닝 트리(MST)

무방향 그래프의 간선들에 가중치가 주어진 경우, 스패닝 트리 중에서 간선들의 가중치 합이 최소인 스패닝 트리를 말한다.

이를 구하는 알고리즘에는 크루스칼과 프림이 있다.

크루스칼(Kruskal) 알고리즘

크루스칼은 그리디하게 모든 정점을 최소 비용으로 연결하여 최소 신장 트리를 구한다.
크루스칼의 핵심은 모든 간선들을 가중치 기준으로 오름차순으로 정렬하고 가중치가 작은 간선부터 차례대로 모든 정점이 연결될 때까지 연결하는 것이다.
Union-Find 알고리즘을 사용하여 구현하며, 이를 통해 사이클이 형성되지 않으면서 모든 정점을 연결할 수 있다.

동작 방식

1. 그래프의 간선들을 가중치 기준으로 오름차순으로 정렬한다.
2. 정점을 연결한다.
   2-1. 정렬된 간선 리스트를 순서대로 선택해서 사이클이 발생하지 않는다면(find 사용, 두 정점의 parent가 달라야 한다.) 스패닝 트리에 포함시킨다.
   2-2. 이때 정점을 연결하는 것은 유니온 파인드의 union으로 구현한다.
3. 만약 간선의 두 정점 a, b가 이미 연결되어 있다면 union 수행 시 사이클이 형성된다는 것을 의미하기 때문에 스킵한다.
4. 위의 과정을 반복하여 최소 비용의 간선들만 이용해 모든 정점이 연결된다.

프림(Prim) 알고리즘

프림도 최소 신장 트리를 구하는 알고리즘이다.
프림은 임의의 시작점에서 현재까지 연결된 정점들에서 연결되지 않은 정점들에 대해 가장 가중치가 작은 정점을선택하여 연결하는 정점 선택 기반으로 동작한다.
프림의 핵심은 트리 집합을 단계적으로 확장하는 것이고, 새로운 정점을 연결할 때마다 새로운 정점에서 갈 수 있는 아직 연결되지 않은 정점들에 대한 간선을 추가해주어야 한다.
우선순위큐를 이용한 최소힙으로 구현할 수 있으며, 다익스트라 알고리즘과 구현방식이 유사하다.

동작 방식

1. 임의의 정점을 시작점으로 선택한다.
2. 시작점에서 갈 수 있는 정점 중 가장 가중치가 작은 정점을 연결한다.
3. 2번 과정에서 시작점과 정점들이 연결되었다.
   3-2. 시작점과 연결된 정점들을 a집합이라 하면, a집합에서 갈 수 있는 a집합에 속하지 않은 정점들에 대해 가중치가 가장 작은 정점을 연결한다.
4. 시작점을 포함한 a집합에 새로운 정점을 연결하여 a집합의 크기가 늘어났다. 위의 과정을 모든 정점이 연결될 때까지 반복한다.

코드

# 유니온 파인드
# 크루스칼
# 최소 신장 트리(최소 스패닝 트리)

# find 함수 : parent를 찾아준다.
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])

    return parent[x]

# union 함수 : 합집합을 만들어준다. (스패닝 트리에 포함, 연결 시키는 것)
def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b


N, M = map(int, input().split())
connects = []
parent = [i for i in range(N+1)]

for i in range(M):
    a, b, c = map(int, input().split())
    connects.append((a,b,c))

# 가중치를 기준으로 정렬한다.
connects.sort(key=lambda x:x[2])

answer = 0
biggest = 0 # 최소 스패닝 트리에서 가장 큰 간선을 빼서 마을을 2개로 분리함

for a, b, c in connects:
    # 사이클이 발생하지 않는다면 트리에 포함시키고 비용 업데이트
    if find(parent, a) != find(parent, b):
        union(parent, a, b)
        answer += c
        biggest = c

print(answer-biggest)