[SWEA] - 하나로 / 1251번 (Java)

[SWEA] - 하나로 / 1251번 (Java)

[SWEA] - 하나로 / 1251번 (Java)

1. 문제 접근

각 섬의 좌표가 주어지고, 각 섬을 연결하고자할 때 섬을 연결하는 최소 비용을 계산 하면 되는 문제다.

 

최소 비용으로 모든 섬을 연결하기 위해 MST(Kruskal) 알고리즘을 통해 구현했다.

 

구현의 흐름은 다음과 같다.

1. 간선의 정보가 주어지지 않았으므로, 완전그래프 형태로 모든 간선을 생성하여 간선 리스트에 저장한다.
2. 간선 리스트를 환경부담금(`cost`)을 기준으로 오름차순으로 정렬한다.
3. 환경부담금(`cost`)이 작은 간선부터 트리에 연결한다.
   • 이 때, 사이클이 생길 경우 해당 간선은 제외한다.
4. 간선의 개수가 V-1(V: 섬 개수)가 된다면 종료한다.

완전 그래프에서 간선의 개수는 V(정점의 개수) * (V - 1) / 2가 된다.

 

추가적으로 입력 내용을 보면, "섬들의 정수인 Y좌표가 주어진다 (0≤X≤1,000,000, 0≤Y≤1,000,000)"라고 명시 되어있다.

 

이 때, 거리의 제곱 값의 최대값는 100만의 제곱이 되는데 이는 `int`형으로는 오버플로우가 발생한다.

 

따라서 가중치를 다루는 변수들은 `long`형으로 처리해야한다.

 

this.distSquare =
        (long)Math.abs(islands[to].x - islands[from].x) * (long)Math.abs(islands[to].x - islands[from].x)+
        (long)Math.abs(islands[to].y - islands[from].y) * (long)Math.abs(islands[to].y - islands[from].y);
this.cost = (double)distSquare * E;

 

---

2. 코드

package swea;

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

/**
 * [SWEA] - 하나로 / 1251번 
 * @author JinHxxxxKim
 * 
 * 1. 전체 테스트 케이스의 수를 입력받는다.
 * 2. 섬의 개수 N을 입력받는다.
 * 3. 각 섬들의 좌표를 입력받는다.
 * 4. 해저터널 건설의 환경 부담 세율 실수 E를 입력받는다.
 * 5. 완전 그래프 형태로 모든 섬에 대한 간선을 생성하여 간선 리스트에 저장한다.
 * 6. 간선 리스트를 환경부담금 기준으로 오름차순으로 정렬한다.
 * 7. MST 알고리즘 실행
 * 
 */
public class Sol_1251 {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	private static StringTokenizer st;
	
	private static int N; // 섬의 개수
	private static int edgeNum; // 간선의 수 
	private static Island[] islands; // 섬 위치 정보 배열
	private static double E; // 세율
	private static Edge[] edgeList; // 간선 리스트
	
	// unionFind 변수
	private static int[] parents;
	
	public static void main(String[] args) throws Exception {
		int TC = Integer.parseInt(br.readLine().trim());
		for (int testCase = 1; testCase <= TC; testCase++) {
			N = Integer.parseInt(br.readLine().trim());
			islands = new Island[N];
			
			// 완전 그래프의 간선의 최대개수
			edgeNum = (N * (N - 1)) / 2;
			
			// 섬 위치 정보 저장
			for (int islandCnt = 0; islandCnt < N; ++islandCnt) {
				islands[islandCnt] = new Island();
			}
			st = new StringTokenizer(br.readLine().trim());
			for (int islandCnt = 0; islandCnt < N; ++islandCnt) {
				int x = Integer.parseInt(st.nextToken());
				islands[islandCnt].x = x;
			}
			st = new StringTokenizer(br.readLine().trim());
			for (int islandCnt = 0; islandCnt < N; ++islandCnt) {
				int y = Integer.parseInt(st.nextToken());
				islands[islandCnt].y = y;
			}
			
			// 세율 입력
			E = Double.parseDouble(br.readLine().trim());
			
			edgeList = new Edge[edgeNum];
			int edgeIdx = 0;
			// 완전 그래프 형태로 간선 저장 (Max: 1000 x 1000)
			for (int node1 = 0; node1 < N; ++node1) {
				for (int node2 = node1; node2 < N; ++node2) {
					if(node1 == node2) continue;
					edgeList[edgeIdx++] = new Edge(node1, node2);
				}
			}
			
			makeSet();
			// 가중치 기준 오름차순 정렬
			Arrays.sort(edgeList);
			
			// MST 알고리즘 실행
			double totalCost = 0;
			int edgeCnt = 0;
			for (Edge currEdge : edgeList) {
				if(union(currEdge.to, currEdge.from)) {
					totalCost += currEdge.cost;
					++edgeCnt;
				}
				if(edgeCnt == N-1)
					break;
			}
			
			sb.append(String.format("#%d %.0f\n", testCase, totalCost));
		}
		System.out.println(sb);
	}

	// unionFind 전처리
	private static void makeSet() {
		parents = new int[N];
		for (int node = 0; node < N; ++node) {
			parents[node] = node;
		}
	}

	// 매개변수로 전달된 node의 루트를 찾는 메소드
	private static int find(int node) {
		if (parents[node] == node)
			return node;
		else
			return parents[node] = find(parents[node]);
	}
	
	// 매개변수로 전달된 node1, node2의 집합을 합치는 메소드
	private static boolean union(int node1, int node2) {
		int aRoot = find(node1);
		int bRoot = find(node2);
		if (aRoot == bRoot)
			return false;
		parents[aRoot] = bRoot;
		return true;
	}
	
	// 섬의 위치 정보 저장
	static class Island {
		int x, y;

		public Island() {
			super();
		}

		public Island(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}

	// 간선 클래스
	static class Edge implements Comparable<Edge> {
		int to, from;
		long distSquare;
		double cost;

		public Edge(int to, int from) {
			super();
			this.to = to;
			this.from = from;
			this.distSquare =
					(long)Math.abs(islands[to].x - islands[from].x) * (long)Math.abs(islands[to].x - islands[from].x)+
					(long)Math.abs(islands[to].y - islands[from].y) * (long)Math.abs(islands[to].y - islands[from].y);
			this.cost = (double)distSquare * E;
		}

		@Override
		public int compareTo(Edge edge) {
			return Double.compare(this.cost, edge.cost);
		}

	}
}

---

3. 디버깅

x, y의 최대 값을 고려하지 않고 `int`형으로 가중치를 관리하고자 한다면 오버플로우가 발생하게 된다.

 

따라서 연산에 따른 자료형 변환에 대해 신경써서 구현해야한다.

 

---

4. 결과