[항해99 코테 챌린지] 최소신장트리, 크루스칼, 프림, 솔린 알고리즘

최소신장트리란?

최소신장트리(Minimum Spanning Tree, MST)는 가중치가 있는 연결 그래프에서 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리이다. 다만 이 때, 사이클이 생기면 안된다.

프림 알고리즘

1. 시작할 임의의 노드를 정하고 MST 트리에 넣는다.

2. MST 트리에 포함된 노드들과 연결된 간선 들 중 가장 작은 가중치를 가진 간선과 정점을 선택후 MST 트리에 삽입한다. (사이클을 막기 위해 MST 트리에 노드가 중복으로 들어가는지 확인(유니온 파인드) 후 만약 중복이라면 그냥 다음 차례로 넘어간다)

3. 2번을 반복하여, MST 트리 내에 정점의 갯수와 원래 트리의 정점 갯수가 같아지면 끝낸다.

 

위 예시 그래프를 보면 진행 과정은 아래와 같이 이루어진다.

1. 시작할 노드 A 선택 후 MST 삽입

2. A에 연결된 간선 중 가장 작은 1(AB) 선택 후 B와 같이 MST 삽입

3. A-B에 연결된 간선들 중 가장 작은 3(BE) 선택 후  E와 같이 MST 삽입

4. A-B-E에 연결된 간선들 중 가장 작은 4(ED) 선택 후  D와 같이 MST 삽입
5. A-B-E-D에 연결된 간선들 중 가장 작은 4(AC) 선택 후  C와 같이 MST 삽입

6. A-B-E-D-C 총 원래 그래프의 노드와 노드구성이 같으므로 종료

 

대학 교재에서는 MST 삽입시 사이클을 포함하는지 확인하라고 되어 있는데.. 이게 다른 데에서는 MST 정점에 이미 있는거랑 연결되는건 무시하고 빼라고 설명 되어 있다. 그게 그거라고 생각하지만 뭔가 설명이 이상하다 ^^;;

크루스칼 알고리즘

1. 모든 간선을 가중치 기준 오름차순으로 정렬한다.

2. 가장 작은 가중치인 간선을 선택 후 MST에 해당 간선과 연결된 노드를 포함한다.

3. 그 다음 작은 가중치를 선택하며, 이 때 이미 MST에 연결된 정점과 연결되는지 (사이클 생성, 유니온 파인드) 확인하고 추가한다.

4. 모든 간선에 대해 2,3 번을 전부 다 돈다. (사이클이 생겨서 무시한다 하더라도)

 

위 예시 그래프를 보면 진행 과정은 아래와 같이 이루어진다.

1. 간선 AB 와 노드 A,B 추가

2. 나머지 간선 중 가장 가중치가 작은 간선 DE와 노드 D,E 추가

3. 나머지 간선 중 가장 가중치가 작은 간선 BE 추가 (사이클이 안 생기므로)

4. 나머지 간선 중 가장 가중치가 작은 간선 AC와 노드 C 추가

5. 나머지 간선들은 사이클이 생기므로 무시

솔린 알고리즘

1. 각 정점을 하나의 포레스트(숲) 으로 보고, 해당 숲이 외부에 연결될 수 있는 가장 최소치인 간선과 정점을 선택한다.

2. 이렇게 완성된 (숲)이 하나로 이어질때 까지 1을 반복한다.

 

위 예시 그래프를 보면 진행 과정은 아래와 같이 이루어진다.

1. A,B,C,D,E 로 각각 이뤄진 5개의 숲 생성

2. 각 숲별로 외부와 연결될 수 있는 최소 간선 선택 (AB, DE, AC)

3. A-(B,C) / D-E 여기서 두 숲을 붙일 수 있는 최소 간선 선택 (BE)

 

유니온 파인드

사이클을 검증하는 과정에서 사용되는 방법. 집합을 관리하고, 두 원소가 같은 집합에 속하는지 확인하는데 사용되는 알고리즘(자료구조) 이다.

1. Find: 주어진 원소가 속한 집합을 찾는 연산.
2. Union: 두 집합을 합치는 연산.

이렇게 두 연산으로 구성되어 있다.

 

어떤 원소가 자신의 부모노드가 무엇인지 따로 저장하고 있다가 (이래서 자료구조라고 설명하기도 한다). 쭈욱~ 루트까지 타고가면서, Find 연산을 통해 같은 트리가 아니라고 판단되면 (즉, 사이클이 안생길거라면) 그 때 Union 연산을 통해 더 큰 집합에다가 붙여서, 한 트리로 만드는 것이다.

 

예를 들면 원소가 1,2,3,4 가 있고 따로 존재하는데, 이걸 합치는 과정을 보도록 하자.

 

1. 1,2,3,4 는 부모노드를 자기 자신으로 저장한다.

노드	1	2	3	4
부모노드	1	2	3	4

 

2. 2를 1에 합치기 위해 각자의 루트노드가 겹치는지 확인 후(부모노드를 따라가면서..) 겹치지 않으면 자신의 부모노드를 1로 변경한다

노드	1	2	3	4
부모노드	1	1	3	4

 

3. 2를 3에 합치기 위해 각자의 루트노드가 겹치는지 확인 후(부모노드를 따라가면서..) 겹치지 않으면 자신의 부모노드를 2로 변경한다

노드	1	2	3	4
부모노드	1	1	2	4

 

4. 3를 4에 합치기 위해 각자의 루트노드가 겹치는지 확인 후(부모노드를 따라가면서..) 겹치지 않으면 자신의 부모노드를 3로 변경한다

노드	1	2	3	4
부모노드	1	2	2	3

 

5. 위 경우는 안 써져 있지만, 경로압축을 확실히 하기 위해 parent 배열을 find_parent 를 통해 한번 더 정리해줘야 한다.

def find_parent(parent, idx):
    # 루트노드가 아니라면 재귀적으로 찾아서 최상위 부모까지 타고 들어가게 한 다음 업데이트
    if(parent[idx] != idx):
        parent[idx] = find_parent(parent, parent[idx])
    return parent[idx]
# 두 원소 합치기
def union_parent(parent, a, b):
    # 각자의 부모를 뽑아, 부모 - 자식관계로 변경
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if(a < b):
        parent[b] = a
    else:
        parent[a] = b

v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(v + 1):
    parent[i] = i
# union 연산을 각각 수행
for i in range(e):
    a, b =  map(int, input().split())
    # 간선 합칠때 사이클 발생하는지 확인
    a_parent = find_parent(parent, a)
    b_parent = find_parent(parent, b)
    if(a_parent == b_parent): 
        print('사이클 발생')
        break
    union_parent(parent,a,b)

# 각 원소가 속한 집합 (가장 루트를 찾아서 반환) -> 경로압축을 확실히 한번 더 해줘야 됨
for i in range(v + 1):
    print(find_parent(parent, i), end=' ')
print()

# 단순 부모 테이블 출력
for i in range(v + 1):
    print(parent[i], end=' ')