[알고스팟] 남극기지 > 최소신장트리 (MST) > 프림 알고리즘

문제: 남극기지

이 문제는 최소신장트리 문제이다. 각 기지를 연결하는 최소 신장 트리에서 각 기지간의 연결 거리 중 가장 큰 값을 찾으면 된다.

이전 포스팅 에서는 Kruskal 알고리즘을 이용해서 문제를 풀었었는데, 본 포스팅에서는 Prim 알고리즘을 이용해서 풀어보겠다.

 프림 알고리즘은 다음과 같이 동작한다.

  1) 시작점을 선택하고 시작점을 추가된 정점의 집합인 MST_V 에 추가한다.

  2) MST_V에 속해 있는 정점과 그렇지 않은 정점 중 최소 간선을 가지는 정점을 MST_V에 추가한다.

  3) 2)를 모든 정점이 MST_V에 들어가게 될 때까지 방복한다.

다음 그림에서 상세하게 설명한다.

다음은 PriorityQueue를 이용해서 구현한 버전이다.

	import java.util.PriorityQueue;
	import java.util.Scanner;
	//465342 ARCTIC alnova2 java 2.5KB 정답 688ms 방금 전
	public class Main {
	//Edge를 PriorityQueue에 추가하면 최소 Distance로 정렬되도록 하는 클래스
	private class edge implements Comparable<edge> {
	private Integer mFrom;
	private Integer mTo;
	private double mWeight;
	public edge(int from, int to, double weight){
	mFrom=new Integer(from);
	mTo=new Integer(to);
	mWeight=weight;
	}
	@Override
	public int compareTo(edge o) {
	// TODO Auto-generated method stub
	return (this.mWeight>=o.mWeight) ? 1:-1;
	}
	}
	//MST_V 에 속하는 정점들과 다른 정점들과의 Edge 를 Distance로 정렬해서 가지고 있는 Queue
	private PriorityQueue<edge> mPQ;
	//MST_V에 속한 정점인지 확인하게 하는 값
	private boolean[] mMST_V;
	private double[][] mDistance;
	private int mNumPosition;
	public Main(int numPosition,double[][] position){
	mNumPosition=numPosition;
	mMST_V=new boolean[mNumPosition];
	mDistance=new double[mNumPosition][mNumPosition];
	mPQ=new PriorityQueue<edge>();
	for(int i=0;i<numPosition;i++){
	double distance;
	for(int j=0;j<numPosition;j++){
	distance=Math.sqrt(Math.pow(position[i][0]-position[j][0], 2.0)+Math.pow(position[i][1]-position[j][1], 2.0));
	mDistance[i][j]=distance;
	mMST_V[i]=false;
	}
	}
	}
	public void MST_Prim(){
	double maxRange=0;
	//0 부터 시작
	mMST_V[0]=true;
	int mIncCnt=1;
	//시작 주변의 Edge를 PriorityQueue에 넣는다
	for(int i=1;i<mNumPosition;i++){
	mPQ.add(new edge(0,i,mDistance[0][i]));
	}
	//Queue에 아무것도 없거나, MST_V에 추가된 정점의 개수가 모든 정점의 개수일때 종료
	while(!mPQ.isEmpty() && mIncCnt<mNumPosition){
	//Edge 중 최소 값을 가지는 것을 추출
	edge next=mPQ.remove();
	//Edge의 연결점이 이미 추가된 정점일 경우 무시
	if(mMST_V[next.mTo]) {
	continue;
	} else {
	if(maxRange<next.mWeight) maxRange=next.mWeight;
	//System.out.println("From:"+next.mFrom+" to:"+next.mTo+" Weight:"+next.mWeight+" maxRange:"+maxRange);
	//MST_V에 새롭게 추가하는 정점의 Edge 를 PriorityQueue에 삽입
	for(int i=0;i<mNumPosition;i++){
	if(!mMST_V[i] && i!=next.mTo) {
	mPQ.add(new edge(next.mTo,i,mDistance[next.mTo][i]));
	}
	}
	//MST_V에 추가
	mMST_V[next.mTo]=true;
	mIncCnt++;
	}
	}
	System.out.printf("%.2f\n", maxRange);
	}
	public static void main(String[] args) {
	// TODO Auto-generated method stub
	Scanner sc=new Scanner(System.in);
	int caseCnt=sc.nextInt();
	for(int caseIdx=0;caseIdx<caseCnt;caseIdx++){
	int numPosition=sc.nextInt();
	double[][] position=new double[numPosition][2];
	for(int i=0;i<numPosition;i++){
	position[i][0]=sc.nextDouble();
	position[i][1]=sc.nextDouble();
	}
	Main solution=new Main(numPosition,position);
	solution.MST_Prim();
	}
	}
	}

view raw MST_Prim_PQ.java hosted with ❤ by GitHub

다음은 정점을 추가할때 다른 정점들과의 거리의 최소값을 저장해서 구현한 버전이다. 다음 그림처럼 MST_V 에 추가된 정점들이 있을 경우에 이 정점들로부터 그 외 정점들까지의 최소 비용을 Update하는 매트릭스를 이용해서 계산한다.

다음은 이를 구현한 코드이다.

	import java.util.Comparator;
	import java.util.HashSet;
	import java.util.LinkedList;
	import java.util.NavigableSet;
	import java.util.PriorityQueue;
	import java.util.Queue;
	import java.util.Scanner;
	import java.util.Set;
	import java.util.TreeSet;
	import java.util.Vector;
	// ARCTIC alnova2 java 2.3KB 정답 644ms 방금 전
	public class Main {
	private boolean[] mMST_V;
	private double[] mEdgeDistanceMin;
	private double[][] mDistance;
	private int mNumPosition;
	public Main(int numPosition,double[][] position){
	mNumPosition=numPosition;
	mMST_V=new boolean[mNumPosition];
	mEdgeDistanceMin=new double[mNumPosition];
	mDistance=new double[mNumPosition][mNumPosition];
	for(int i=0;i<numPosition;i++){
	double distance;
	for(int j=0;j<numPosition;j++){
	distance=Math.sqrt(Math.pow(position[i][0]-position[j][0], 2.0)+Math.pow(position[i][1]-position[j][1], 2.0));
	mDistance[i][j]=distance;
	mMST_V[i]=false;
	mEdgeDistanceMin[i]=Integer.MAX_VALUE;
	//System.out.println(i+" to "+j+" = "+mDistance[i][j]);
	}
	}
	}
	private int findMinKey(){
	int minKey=Integer.MAX_VALUE;
	double min=Double.MAX_VALUE;
	for(int i=0;i<mNumPosition;i++){
	if(mMST_V[i]==false && mEdgeDistanceMin[i]<min){
	minKey=i;
	min=mEdgeDistanceMin[i];
	}
	//System.out.print(mKeys[i]+" ");
	}
	//System.out.println(" Ret:"+minKey);
	return minKey;
	}
	public void calculate(){
	double maxRange=0;
	mMST_V[0]=true;
	mEdgeDistanceMin[0]=0;
	for(int i=1;i<mNumPosition;i++){
	mEdgeDistanceMin[i]=mDistance[0][i];
	}
	for(int i=1;i<mNumPosition;i++){
	int nextNode=findMinKey();
	mMST_V[nextNode]=true;
	if(maxRange<mEdgeDistanceMin[nextNode]) maxRange=mEdgeDistanceMin[nextNode];
	//System.out.println(" Add:"+nextNode+" max:"+maxRange);
	for(int j=0;j<mNumPosition;j++){
	if(mMST_V[j]==false && mEdgeDistanceMin[j]>mDistance[nextNode][j]){
	mEdgeDistanceMin[j]=mDistance[nextNode][j];
	}
	}
	}
	System.out.printf("%.2f\n", maxRange);
	}
	public static void main(String[] args) {
	// TODO Auto-generated method stub
	Scanner sc=new Scanner(System.in);
	int caseCnt=sc.nextInt();
	for(int caseIdx=0;caseIdx<caseCnt;caseIdx++){
	int numPosition=sc.nextInt();
	double[][] position=new double[numPosition][2];
	for(int i=0;i<numPosition;i++){
	position[i][0]=sc.nextDouble();
	position[i][1]=sc.nextDouble();
	}
	Main solution=new Main(numPosition,position);
	solution.calculate();
	}
	}
	}

view raw MST_Prim_Matrix.java hosted with ❤ by GitHub