최소 신장 트리(Mininum Spannig Tree, MST)

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

17472번: 다리 만들기 2

삼성 SW 역량테스트 A+을 좌절시킨 그 문제이다. 테스트를 볼 때는 최소 신장 트리 개념조차 몰라서 풀지 못했던 문제..

 

 

최소 신장 트리

무방향 가중치 그래프에서 최소 가중치의 합으로 모든 Node가 연결되도록 하는 Edge들의 부분집합.

n개의 Node가 그 Edge의 가중치가 주어질 때, 최소의 비용으로 모든 Node가 연결되도록 하는 문제의 풀이에 사용되는 개념이다. Node와 Node를 잇는 Edge가 하나라는 법은 없고 그 가중치 또한 각각 다를 수 있기 때문에 최소 신장 트리는 1개일수도 있지만 여러개일수도 있다. 위의 다리 만들기 2 문제도 전형적인 최소 신장 트리를 만드는 문제이다.

 

 

왜 Tree라고 하는가?

부모 - 자식 간의 계층적 구조를 갖는 자료구조가 Tree이지만, 사이클이 없는 무방향 그래프도 Tree 구조를 가질 수 있다.

만약 사이클이 생긴다면 Node의 중복연결이 생기기 때문에 모든 가중치의 합이 최소가 되어야한다는 조건을 충족시킬 수 없다.

 

 

Kruskal 알고리즘

최소 신장 트리(이하 MST)를 만드는 대표적인 알고리즘 중 하나다.

• Edge들의 가중치를 오름차순으로 정렬한다.
• Edge를 처음부터 순회한다. 단 이미 선택된 Edge의 집합과 현재 선택한 Edge가 사이클을 생성할 경우 선택하지 않는다.
• Node 갯수-1개만큼의 Edge를 선택하면 순회를 종료한다.

다음의 과정으로 MST를 생성한다.

 

사이클을 만들지 않는 법

A, B, C, D, E, F 6개의 Node가 있다고 해보자.

 

그렇다면 이 6개의 Node를

{A}, {B}, {C}, {D}, {E}, {F}

이렇게 각 Node를 집합으로 생각할 수 있다.

 

그리고 만약 A와 B를 연결한다면 

{A, B}, {C}, {D}, {E}, {F}

이렇게 하나의 집합으로 연결한다.

Node를 순회하면서 연결하고자 하는 두 Node가 같은 집합 안에 포함되어 있다면 연결 시 사이클이 생성된다.

 

같은 집합에 속해있는지 아닌지 확인하는 법

set이나 array에 Node를 넣고 하나씩 확인한다면 각 Node를 탐색할때마다 최악의 경우 O(n)을 2번 해야하고, 이걸 각 Node를 거칠때마다 진행한다면 매우 비효율적인 탐색 방식을 갖게 된다.

이를 효과적으로 집합의 형태로 저장하기 위해, Tree 구조로 저장한다.

 

A, B, C, D, E, F, G 7개의 Node가 있고, 이 각 Node 가중치의 오름차순으로 정렬하면 다음과 같다.

 

A - D : 5

C - E : 5

D - F : 6

A - B : 7

B - E : 7

B - C : 8

E - F : 8

B - D : 9

E - G : 9

F - G : 11

D - E : 15

 

다음과 같다.

[A, B, C, D,E, F, G]를 [1, 2, 3, 4, 5, 6, 7]로 지정한다. 현재까지는 자기 자신의 부모는 자기 자신이다.

Union-find를 이용해 부모를 찾아간다.

def find_parent(node, parents):
    if parents[node] == node:
        return node
    root = find_parent(parents[node], parents)
    return root

자기 자신의 부모가 자기 자신일때까지 부모를 탐색하며 올라간 후 가장 마지막의 Node를 return하면 맨 위의 부모를 return하게 된다.

 

이렇게 2개의 Node의 부모를 찾은 뒤 같은 부모를 공유하고 있다면 같은 집합 안에 포함되어 있는 것으로 보고 MST를 구성하지 않는다.

 

만약 같은 부모를 공유하지 않는다면 서로 다른 집합에 속해있기 때문에 이를 MST에 포함시키고, 같은 부모를 공유하도록 부모를 일치시킨다.

 

def find_parent(node, parents):
    if parents[node] == node:
        return node
    root = find_parent(parents[node], parents)
    return root

parents = [x for x in range(Node 갯수+1)]

x, y = find_parent(first_node, parents), find_parent(second_node, parents)

if x != y:
    parents[x] = y

 

트리의 높이를 최대한 낮게 해 Union-Find의 효율성을 높일 수 있다.

size = [1 for _ in range(num+1)] # 각 집합의 size는 1로 초기화
parents = [x for x in range(Node 갯수+1)]

x, y = find_parent(first_node, parents), find_parent(second_node, parents)

if x != y:
    if size[x] > size[y]: # node 갯수가 많은 쪽의 집합으로 종속시킨다
        parents[y] = x # x가 더 크므로 y의 부모를 -> x로
        size[x] += size[y] # x의 크기는 y만큼 증가
    else:
        parents[x] = y
        size[y] += size[x]

 

path compression(경로 압축)을 이용해 중복되는 계산을 줄이는 방법도 Union-Find의 효율성을 높일 수 있는 방법이다.

def find_parent(node, parents):
    while node != parents[node]:
        parents[node] = parents[parents[node]]
        node = parents[node]
    return parents[node]