[SWEA] 1251. 하나로

문제

1251. [S/W 문제해결 응용] 4일차 - 하나로
인도네시아 내의 N개의 섬들 사이에 해저터널을 설치해서 하나로 연결한다.
이때 환경부담금이 가장 적게 만드는 경우의 환경부담금을 구하라.

환경부담금 : E*(L^2)
L^2 = (x1-x2)^2 + (y1-y2)^2

풀이

Prim 알고리즘을 사용했다.
처음엔 Kruskal을 사용하려고 했었는데, 간선이 주어진 게 아니라 모든 경우의 수를 고려해야 하기 때문에 전체 간선의 비용을 구해서 정렬하는 과정이 비효율적이라고 느꼈다. 그리고 set 여러 개를 관리하는 게 너무 복잡했다! 그래서 덜 직관적이지만 비교 횟수가 적을 것 같은 Prim을 사용했다.

• Prim알고리즘 구현
• Island클래스 선언 (num 번호, p 연결된 섬, key 환경부담금)
• final int END 를 선언해두고, 터널이 확정된 섬은 END로 표시해줬다.
  (pq를 사용하지 않고 list를 사용해서 확인한 섬은 지우는 대신 END 처리)
• getMin() 에서 터널이 확정되지 않은 섬들 중 환경부담금이 가장 작은 섬을 얻는다.
• 나머지 섬들의 환경부담금을 갱신시켜준다.
• 마지막에 모든 섬의 key값을 더해서 출력한다.

자바코드

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;

import java.io.FileInputStream;


class Solution
{
	static int N;
	static double E;
	
	static int [] x;
	static int [] y;
	
	static Island [] il;
	static final double INF = Double.MAX_VALUE;
	static final int NS = -1; // not start
	static final int END = -2; // finish

	public static void main(String args[]) throws Exception
	{

		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++)
		{
			N = sc.nextInt();
			il = new Island[N];
			x = new int[N];
			y = new int[N];
			
			for (int i=0; i<N; i++) {
				x[i] = sc.nextInt();
			}
			for (int i=0; i<N; i++) {
				y[i] = sc.nextInt();
			}
			E = sc.nextDouble();
			
			for (int i=0; i<N; i++) {
				il[i] = new Island(i);
				il[i].key = INF;
			}
			
			prim();
			
			double answer = 0;
			for (int i=0; i<N; i++) {
				answer += il[i].key;
			}
			
			System.out.printf("#%d %d\n", test_case, Math.round(answer));
		}
	}
	
	public static void prim() {
		ArrayList<Island> list = new ArrayList<>();
		
		for (int i=0; i<N; i++) {
			list.add(il[i]);
		}
		// 시작
		il[0].key = 0.0;
		il[0].p = 0;
		
		Island cur;
		
		while(true) {
			cur = getMin(list);
			if (cur == null) break;
			cur.p = END; // 확인한다 표시 
			for (int i=0; i<N; i++) {
				if (il[i].p == END) continue;
				double length = (Math.pow(x[cur.num]-x[il[i].num], 2)+Math.pow(y[cur.num]-y[il[i].num], 2))*E;
				if (il[i].key > length) {
					il[i].key = length;
					il[i].p = cur.num;
				}
			}
		}
	}

	static class Island {
		int num;
		int p;
		double key;
		Island() {}
		Island(int num) {
			this.num = num;
			this.p = NS;
			this.key = INF;
		}
	}
	
	static Island getMin(ArrayList<Island> list) {
		Island min = null;
		for (int i=0; i<N; i++) {
			if (list.get(i).p == END) continue; // 이미 끝난거 
			if (min == null) { // 최초설정 
				min = list.get(i);
				continue;
			}
			if (list.get(i).key < min.key) { // 작은 값을 가진 섬으로 갱신 
				min = list.get(i);
			}
		}
		return min;
	}
}

틀린 이유

• PriorityQueue는 값을 넣을 때 root로 갱신되는데, pq에 넣고나서 값을 바꾸니까 환경부담금이 가장 작은 섬을 확인할 때 엉뚱한 섬이 나왔었던 것으로 추정된다.
• 출력시 범위가 초과됨!
  1차시도 : 결과 출력할 때 E를 곱했었는데, 그때 그때 E를 곱해주었다. (범위랑은 크게 관련이 없지만 마지막에 E를 곱했다면 오차가 생겼을 듯)
  2차시도 : Island의 key를 double로 변경
  3차시도 : 마지막에 환경부담금을 더하는 변수의 타입이 int였다 ^^.. -> double로 변경 ㅜ