프로그래머스 문제를 풀다가 크루스칼 알고리즘이라는 것과 마주치게 되었다.
처음 접하는 알고리즘이라 생각했지만, 이에 대해 찾아보면서 나는 기억하게 된다.
1학년 시절 이산수학 시간에 크루스칼 알고리즘과 프림 알고리즘에 대해 배웠다는 것을..
손과제도 했었지.. 그 때는 정말로 이해가 안됐어..
3년이 지난 지금에서야 다시 정리해보려 한다.
Minimum Spanning Tree
: 최소 신장 트리, 최소 스패닝 트리
: 가중치 무방향 그래프에서 모든 정점을 최소 비용으로 연결할 수 있는 방법
위와 같이 간선에 가중치가 있고, 방향이 없는 그래프를 가중치 무방향 그래프라고 합니다.
그리고 그래프 위의 모든 정점을 최소 비용으로 탐색하는 방법을 찾고자 합니다.
이 때 생각해볼 수 있는 것은, 최소 비용이 되려면 사이클을 형성하지 않아야 한다는 것입니다.
위의 그림과 같이 간선을 선택한 경우에 우리는 "사이클이 발생했다"고 합니다.
이 경우 간선을 하나 제외하더라도 3개의 정점은 이미 연결된 상태임을 알 수 있을 것입니다.
즉, 사이클 == 불필요하게 간선을 하나 더 추가한 상태라는 거죠.
따라서 사이클이 존재한다면 비용이 최소가 될 수 없고,
간선의 수가 (정점-1)개 일 때 최소의 비용을 가지게 됩니다.
위의 그래프에서 MST를 나타내면 다음과 같습니다.
위의 두 가지 모두 정답이 될 수 있습니다.
즉, 하나의 그래프에서 최소 스패닝 트리는 하나 이상 존재할 수 있습니다.
그렇다면 저는 위 그래프에서 Minimum Spanning Tree를 어떻게 찾을 수 있었을까요?
바로 Minimum Spanning Tree를 찾는 알고리즘을 이용하면 됩니다.
오늘은 Minimum Spanning Tree를 찾는 알고리즘 중에서도 가장 유명한 두 방법,
Kruskal Algorithm과 Prim Algorithm에 대해 이야기해보려 합니다.
Kruskal Algorithm
: 크루스칼 알고리즘
: 간선을 기준으로 트리 형성
뒤에서 설명할 프림(Prim) 알고리즘은 "정점"을 기준으로 트리를 형성합니다.
그에 반해, 크루스칼(Kruskal) 알고리즘은 "간선"을 기준으로 트리를 형성합니다.
풀어 설명하면, "가중치가 작은 간선부터 선택하겠다" 입니다.
가중치가 가장 작은 1의 간선을 추가하고, 그 다음으로 작은 2의 간선을 추가합니다.
그 다음으로 작은 가중치는 3인데, 가중치 3을 가진 간선은 (1,2), (1,3), (2,3), (3,4)로 총 4개가 있습니다.
그러나 (1,2)를 택하게 되면 사이클이 발생하게 되므로, 나머지 3가지 중 하나를 선택해야 합니다.
저는 (2,3)을 선택하도록 하겠습니다.
그리고 여전히 가장 작은 가중치인 3의 간선 중 하나를 택하면 됩니다.
(1,3) 또는 (3,4)를 택하여 모든 정점이 연결된 Minimum Spanning Tree를 얻을 수 있습니다.
크루스칼 알고리즘을 실제 코드로 구현하는 방법은 여기에서 설명하도록 하겠습니다.
Prim Algorithm
: 프림 알고리즘
: 정점을 기준으로 트리를 형성
앞에서 말했듯이 크루스칼(Kruskal) 알고리즘은 "간선"을 기준으로 트리를 형성한다면,
프림(Prim) 알고리즘은 "정점"을 기준으로 트리를 형성합니다.
이번에는, 정점을 하나 골라 거기서부터 시작하게 됩니다.
저는 정점 1에서부터 시작해보겠습니다.
그리고 정점 1이 가진 간선들 중 가장 작은 가중치를 가진 간선을 선택합니다.
이제 연결된 정점 0으로 이동해 똑같은 작업을 반복합니다.
정점 0이 가진 간선들 중 이미 선택한 간선을 제외하고 가장 작은 가중치를 가진 간선을 선택합니다.
위 작업을 (사이클이 발생하지 않도록) 반복하여
모든 정점을 방문하는 Minimal Spanning Tree를 얻을 수 있습니다.
그리고 정점 1이 아니라, 2 또는 4에서 시작한다면 아래와 같은 MST를 얻을 수 있겠습니다.
'Computer Science > 알고리즘' 카테고리의 다른 글
| [알고리즘] Kruskal Algorithm, Union Find (크루스칼 알고리즘, 유니온 파인드) (3) | 2021.04.29 |
|---|