[문제풀이] MST 문제 리뷰

MST

Minimum Spanning Tree 로 cycle이 없는 그래프와 같은 Vertex(V), Edge(E)의 최소 Cost를 구하는 알고리즘 (여기서 최소 Cost란 각 Edge별 Cost가 아닌, Node 전체를 거치는데 걸리는 비용을 의미함)

대충 아래와 같은 그래프가 있다고 가정 해보자

여기서 각 Node [A],[B],[C],[D],[E],[F] 는 Vertext(V)가 될 것이고

간선들은 Edge ([A To B:1][B To C:3][A To C:3][A To D:5]등등)가 (E) 될 것이다.

각 edge 별 cost가 가장 낮은 녀석들을 우선순위 Q에다가 집어넣어, 유니온 파인드 알고리즘으로 Root node를 판별 후 모든 Cost의 비용을 합치면 MST의 최소 비용이 나온다.

이게 무슨말?!?

Union Find Algorithm

유니온 파인드 알고리즘을 이용하면 연결된 각 노드별로 Root노드가 되는 녀석을 정의 할 수 있다.
요약: 일련의 과정을 거쳐 연결된 녀석들 중 부모노드를 확인 가능

유니온+크루스칼 대해 자세한 설명을 위해 코드를 보자

import sys
input = sys.stdin.readline

# 1. 유니온 파인드용 함수 정의
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 경로 압축
    return parent[x]

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

# 2. 입력 처리
V, E = map(int, input().split())  # 정점 개수, 간선 개수
edges = []

for _ in range(E):
    a, b, c = map(int, input().split())
    edges.append((c, a, b))  # 가중치, 정점1, 정점2

# 3. 간선 정렬
edges.sort()  # 가중치 기준 오름차순

# 4. Union-Find용 parent 배열 초기화
parent = [i for i in range(V + 1)]  # 정점 번호는 1번부터 V번까지

# 5. MST 구성
total_cost = 0
for cost, a, b in edges:
    if find(a) != find(b):  # 사이클이 생기지 않으면
        union(a, b)
        total_cost += cost

print(total_cost)

설명:

parent: 각 노드별 부모를 저장할 변수 = edges와 인덱스로 연동
edges: Cost, a_node, b_node: edges에는 3가지 정보가 튜플로 들어가며, 간선 비용, 출발지, 목적지를 가리키는 원소들이 들어간다.
간선들을 cost순으로 오름차순 정렬

반복문으로 edges에 간선들을 채워 나감.

• edges를 전체 순회하며 반복문 진행
• union()함수로 현재 노드의 루트노드의 루트노드를 확인 및 루트노드를 업뎃
• 각 노드의 Root노드가 변경될 때만 cost를 total_cost에 누적

과정 그림 설명

코드에서 for cost, a, b in edges: 의 값은 그림에서 a = PN(parent node) b = CN (current node) 로 대체 하겠다.

최초 입력값 받을 시

edges에는 각 간선 정보, Parent 변수에는 부모노드가 적재되어 있다.
(0번 idx 값은 쓰지 않음)

edges Cost순으로 정렬

위문제는 Parent노드까지의 최소비용을 구하는 문제로,
크루스칼 알고리즘의 조건에 의해
간선정보를 오름차 순으로 정렬 할 필요가 있다.

반복문으로 edges 순회 - 1회차

처음 반복문을 돌기 전에 Parent 리스트에는 자기 자신의 번호를 parent로 가지고 있다.
if문으로 PN의 부모와 CN의 부모가 같지 않으면, union()함수를 실행해서 PN에 부모노드를 CN의 부모노드로 지정해버린다.
즉, 3번노드의 부모는 1번으로 변경된다.

• total_cost 에 cost 값을 누적 = 1

반복문으로 edges 순회 - 2회차

다음 edges로 넘어가서 다시 if문을 비교해 보면 또 PN과 CN의 부모가 다른 것을 확인하고 if문 안에 union 함수를 호출 union 함수내부를 보면 x,y의 부모를 찾아서 y에다가 x의 부모 값을 넣는 것을 확인 할 수 있다.
즉 이번 분기에 경우에는 PN=2, CN=3이고,
3의 Root인 1에 parent 리스트에 2의 Root인 2를 삽입 시키는 것이다.

• +total_cost 에 cost 값을 누적 = 1+1

반복문으로 edges 순회 - 3회차

3회차에서는 4,6의 간선의 값을 if문으로 비교. 역시 부모가 같지 않기에, union()함수 실행되어 6노드의 부모 업데이트

• total_cost 에 cost 값을 누적 = 1 + 1 + 2

반복문으로 edges 순회 - 4회차

4회차에는 if문 내용과 같이 부모가 같아 False.
if내부를 거치지 않아 아무런 작업도 이뤄지지 않는다.

반복문으로 edges 순회 - 5회차

5회차에는 FN과 CN은 5,7 의 값으로 각 노드가 각각의 부모를 가지고 있기에 7노드의 부모가 5로 업데이트.

• total_cost 에 cost 값을 누적 = 1 + 1 + 2 + 3

반복문으로 edges 순회 - 6회차

6회차에서는 4의 부모노드가 4에서 2로 업데이트.

• total_cost 에 cost 값을 누적 = 1 + 1 + 2 + 3 + 4

반복문으로 edges 순회 - 7회차

7회차 FN,CN은 6,7이며, 표에 나와 있는 것만 보면 7의 부모노드는 4로 업데이트 될 것으로 생각 할수도 있다.
하지만 코드를 보면
parent[x] = find(parent[x]) 와 같이 재귀함수로 되어 있는 것을 알 수 있다.
즉, 6 -> 4 -> 2 까지 가게되어 parent 리스트의 7node(7번 인덱스)는 2로 업데이트 될 것이다.

• total_cost 에 cost 값을 누적 = 1 + 1 + 2 + 3 + 4 + 4

반복문으로 edges 순회 - 8회차

8회차 또한 7회차와 마찬가지로 find()함수로 4-> 2 순으로 타고 올라가서
5의 부모노드는 2로 업데이트 된다.
이후 if문이 False 내부 함수 실행이 되지 않기 떄문에 cnt 없음.

• total_cost 에 cost 값을 누적 = 1 + 1 + 2 + 3 + 4 + 4

반복문으로 edges 순회 - 9회차

9회차에 경우에도 이미 Root(pareent) 노드가 같기 때문에 별도의 작업이 없고,
이렇게 반복문을 모두 순회하면서 MST가 완성 된다.
total = 15