반응형
문제: 남극기지
이 문제는 최소신장트리 문제이다. 각 기지를 연결하는 최소 신장 트리에서 각 기지간의 연결 거리 중 가장 큰 값을 찾으면 된다.
최소 신장 트리는 각 노드 들간의 거리 값이 주어졌을 때, 이 노드의 거리 값이 최소인 트리를 구성하는 것이다. 프림과 크루스컬 알고리즘이 있다.
이번 포스팅은 크루스컬 알고리즘으로 이 문제를 풀어 보겠다. 일단 크루스컬 알고리즘은 다음과 같이 동작한다.
1) 간선 중 비용이 적은 순으로 소트
2) 1)의 간선 중 사이클을 생성하는 간선을 제외하고 최소 비용의 간선을 추가
3) 2)를 반복함
다음은 WiKi의 내용이다. (크러스컬_알고리즘)
여기에서 핵심은 간선 추가하는데, 간선을 추가할때 Cycle이 생성되는지 확인하는 것이 필요하다. 이를 위한 방법 중 하나는, 간선을 추가할 때마다 연결된 노드들의 집합을 가지고 있다가, 추가하는 간선의 연결된 두 노드 A,B가 같은 집합에 속해 있는지 확인하는 방법이 있다. 예를 들어 다음의 Graph에서 연결된 노드의 집합은 {A,B} ,{C,D}, {E,F,H}, {G,I} 가 있다.
여기에서 F-H 사이의 간선을 추가하게 되면 F,H는 같은 노드 집합에 들어 있기 때문에 Cycle이 생성된다. Cycle이 생성되지 않는 조건은 추가하는 간선을 구성하는 노드가 서로 다른 연결 집합에 있어야 하는 것이다.
다음은 Kruskal 알고리즘을 이용해서 구현한 코드이다.
반응형
