반응형
문제: 남극기지
이 문제는 최소신장트리 문제이다. 각 기지를 연결하는 최소 신장 트리에서 각 기지간의 연결 거리 중 가장 큰 값을 찾으면 된다.
이전 포스팅 에서는 Kruskal 알고리즘을 이용해서 문제를 풀었었는데, 본 포스팅에서는 Prim 알고리즘을 이용해서 풀어보겠다.
프림 알고리즘은 다음과 같이 동작한다.
1) 시작점을 선택하고 시작점을 추가된 정점의 집합인 MST_V 에 추가한다.
2) MST_V에 속해 있는 정점과 그렇지 않은 정점 중 최소 간선을 가지는 정점을 MST_V에 추가한다.
3) 2)를 모든 정점이 MST_V에 들어가게 될 때까지 방복한다.
다음 그림에서 상세하게 설명한다.
다음은 PriorityQueue를 이용해서 구현한 버전이다.
다음은 정점을 추가할때 다른 정점들과의 거리의 최소값을 저장해서 구현한 버전이다. 다음 그림처럼 MST_V 에 추가된 정점들이 있을 경우에 이 정점들로부터 그 외 정점들까지의 최소 비용을 Update하는 매트릭스를 이용해서 계산한다.
다음은 이를 구현한 코드이다.
반응형
