2023.05.17[최소 신장 트리]

📖오늘 배운  것

Spanning Tree

: 그래프 내의 모든 정점을 포함하는 트리

=> 모든 정점들이 연결되어 있고 n개의 정점을 갖는 경우 (n-1)개의 간선으로 연결된다.

 

최소 신장 트리(MST = Minimum Spanning Tree)

: Spanning Tree 중 사이클을 만들지 않고 간선들의 가중치 합이 최소인 트리

=> 각 간선의 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것. 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는 것이 아님!

ex) 통신망, 도로망, 유통망 등... 어떤 그래프 형태에서 길이, 구축 비용, 전송 시간 등을 최소로 구하는 경우

 

MST 구현 방법

1. 크루스칼 알고리즘

: 그리디(탐욕법) 알고리즘 중 하나

-> 그래프의 모든 정점을 사이클 없이 최소 비용으로 연결하는 최적 해답을 구하는 것

사이클을 생성하는지 판단하는 것이 Union-find 자료구조이다.

 

* Union-find란?

: 서로소 집합을 표현하는 자료구조

-> 서로 다른 두 집합을 병합하는 union 연산 + 집합 연소가 어떤 집합에 속해있는지 찾는 find 연산

- union-find 에서는 각 노드가 연결된 최소 노드를 root 노드로 갖게 된다.

따라서 각 노드를 비교하면서 작은 값을 부모 노드로 저장한다. 부모 노드를 기준으로 union 연산에 의해  합쳐지게 되는 것! 만약 이미 부모 노드가 같다면? 연결된 상태이기 때문에 제외하고 다음으로 넘어가면 된다.

 

2. Prim MST 알고리즘

: 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장 해나가는 방법

 

 

관련 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42861 

풀이완

프로그래머스

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

1197번: 최소 스패닝 트리

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

1922번: 네트워크 연결

 

 

참고

https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

https://chanhuiseok.github.io/posts/algo-33/

 

💭배운 점

이게 무슨 알고리즘인가.. 싶었지만 개념을 알고보니 그렇게 어려운 개념은 아니었다! 관련 문제를 풀어보면서 익숙하게 사용할 수 있게 되는 것이 관건일 것 같다. 오늘 관련 문제 좀 더 풀어봐야지!