[SWEA-1251] 하나로 (PRIM)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD

SW Expert Academy

 

이번에는 하나로를 PRIM 방식으로 풀어보려고 한다. 

PRIM 방식은 임의의 한 점을 시작으로, 더 짧은 간선을 찾아가는 그리디 방식의 알고리즘이다. 

 

가장 짧은 점을 저장해 줄거라서, 점들을 비교하기 위해 큰 값을 넣어서 초기화한다.

 

1) 최소점 찾기

2) 최소점부터 다른 점들의 거리를 비교해서 더 짧은 길로 갱신해주기.

이 두 과정을 반복하면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 하나로 {
	//SWEA 문제
	private static int N;
	private static long[][] adjMatrix;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(in.readLine());
		
		for(int t=1; t<=TC; t++) {
			N = Integer.parseInt(in.readLine());
			int x[] = new int[N]; //각 섬의 x좌표
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			for(int i=0; i<N; i++) {
				x[i] = Integer.parseInt(st.nextToken());
			}
			int y[] = new int[N]; //각 섬의 y좌표 
			st = new StringTokenizer(in.readLine(), " ");
			for(int i=0; i<N; i++) {
				y[i] = Integer.parseInt(st.nextToken());
			}
			
			//각 섬끼리의 거리 저장해주기
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					adjMatrix[i][j] = getDistance(x[i], x[j], y[i], y[j]);
					adjMatrix[j][i] = adjMatrix[i][j];
				}
			}
			
			double E = Double.parseDouble(in.readLine());
			System.out.println("#"+t+" "+Math.round(makeMST()*E));
		}
		
	}
	
	private static long makeMST() {
		long [] minEdge = new long[N];
		boolean[] visited = new boolean[N];
		
		//prim 알고리즘 사용할 거라 모든 점 최대값으로 설정.
		Arrays.fill(minEdge, Integer.MAX_VALUE);
		minEdge[0]= 0; //임의의 점인 0번 인덱스를 시작점으로 만들어주기
		
		long result = 0; //최소신장트리 비용
		int cnt = 0; //정점 개수
		
		while(true) {
			long min = Integer.MAX_VALUE;
			int minNo = 0;
			for(int i=0; i<N; i++) { //최소점 찾기
				if(!visited[i] && min > minEdge[i]) {
					minNo = i;
					min = minEdge[i];
				}
			}
			//최소 점 찾았으니 방문 처리 후 정점 값 더해주기
			visited[minNo] = true;
			result += min;
			if(++cnt == N) break;
			//최소점부터 다른 점들 거리 더 짧은 길로 갱신
			for(int i=0; i<N; i++) {
				if(!visited[i] && minEdge[i] > adjMatrix[minNo][i]) {
					minEdge[i] = adjMatrix[minNo][i];
				}
			}
			return result;
		}
		return 0;
	}
	
	static long getDistance(int x1, int x2, int y1, int y2) {
		return (long)(Math.pow(x1-x2, 2) + Math.pow(y1-y2, 2));
	}
}