프로그래머스 문제를 풀던 중 전혀 모르는 문제에 직면하게 되었다...
찾아보니 MST를 찾는 문제로 이를 해결하기 위한 알고리즘이 존재한다는 것과, 내가 이를 수업시간에 공부했었다는 것을 알게 되었다.
알고리즘 A+ 이었는데...
군대가 문제일까 내 머리가 문제일까..
이번 기회에 알고리즘 문제만 풀게 아니라, 자료구조와 알고리즘을 한번 정리해보려한다.
Minimum Spanning Tree
MST는 연결마다 가중치가 있는 무방향 그래프에서 모든 노드를 최소의 비용으로 연결하는 방법에 대한 것입니다.
주로 제가 풀었던 문제처럼 섬을 연결하거나,
도시간의 도로 연결,
네트워크 연결 등
최소 비용으로 노드들을 연결해야하는 문제들은 대부분 Minimum Spanning Tree로 해결 가능하다고 생각하면 될 것 같습니다.
자세한 사항을 설명드리면,
아래와 같은 그래프가 있다고 가정하고 설명드리겠습니다.
해당 그래프에서 MST는 아래 이미지처럼 총 4개의 연결이 될 것 입니다.
MST의 특징
MST의 가장 큰 특징은
1. [사이클이 만들어지지 않아야 한다.]
2. [전체 노드(n) - 1 개의 연결(간선)으로 구성된다.]
입니다.
PS. 추가적인 특징으로 하나의 그래프에 여러개의 MST가 존재할 수 있습니다.
1. 사이클이 만들어지지 않아야한다.
우선 사이클이 만들어지지 않아야하는 이유는,
아래의 그림처럼 사이클이 만들어지는 경우, 불필요한 연결이 생성되게 됩니다.
즉 사이클에 해당하는 연결 중 하나를 제거해도, 모든 노드의 연결이 가능하기 때문에, 사이클은 곧 불필요한 연결이 있다는 증거입니다.
2. 전체노드(n) - 1개의 연결(간선)으로 구성된다.
다음 특징은 [전체 노드(n) -1 개의 연결(간선)으로 구성된다] 입니다.
위에서 설명한 내용과 일맥상통하는 부분이라고도 볼 수 있을 것 같습니다.
불필요한 연결이 존재하지 않아야 하기 때문에 아래의 이미지 처럼 전체 노드를 연결할 때, 필요한 최소의 연결인 n-1개의 연결만 있어야 합니다.
대표적으로 MST를 구하기 위한 알고리즘에는 Kruskal Algorithm과 Prim Algorithm이 있는데 이는 이후에 다루도록 하겠습니다.
음...