[SWEA] 1251.하나로

Kruskal Algorithm

• 메모리 : 96,264 KB

• 실행시간 : 878 ms

• 코드길이 : 2,387 B

• 소요시간 : 1H

package SWExpert;

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

public class Solution_D4_1251_하나로_Kruskal {

	static long[] X;
	static long[] Y;
	static long[][] graph;
	static int[] parents;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder answer = new StringBuilder();
		int T = Integer.parseInt(in.readLine());

		for (int tc = 1; tc <= T; tc++) {
			answer.append('#').append(tc).append(' ');
			int N = Integer.parseInt(in.readLine());
			X = new long[N];
			Y = new long[N];
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			for (int i = 0; i < N; i++) {
				X[i] = Long.parseLong(st.nextToken());
			}
			st = new StringTokenizer(in.readLine(), " ");
			for (int i = 0; i < N; i++) {
				Y[i] = Long.parseLong(st.nextToken());
			}

			double E = Double.parseDouble(in.readLine());
			int size = N * (N - 1) / 2;
			graph = new long[size][3];
			int cnt = 0;
			for (int i = 0; i < N - 1; i++) {
				for (int j = i + 1; j < N; j++) {
					graph[cnt][0] = i;
					graph[cnt][1] = j;
					graph[cnt][2] = (long) (Math.pow(X[i] - X[j], 2) + Math.pow(Y[i] - Y[j], 2));
					cnt++;
				}
			}

			Arrays.sort(graph, new Comparator<long[]>() {
				@Override
				public int compare(long[] o1, long[] o2) {
					return Long.compare(o1[2], o2[2]);
				}

			});

			parents = new int[N];
			for (int i = 0; i < N; i++) {
				makeSet(i);
			}
			cnt = 0;
			double result = 0;
			for (int i = 0; i < size; i++) {
				int a = findSet((int) graph[i][0]);
				int b = findSet((int) graph[i][1]);
				// 같은 팀이라면 패스
				if (a == b)
					continue;
				// 간선이 연결하는 두 정점이 같은 팀이 아니라면 한팀으로 합쳐주고 간선선택
				union(a, b);
				result += graph[i][2];
				cnt++;
				if (cnt == N - 1)
					break;
			}
			result *= E;
			answer.append(Math.round(result)).append('\n');
		}

		System.out.print(answer);
		in.close();
	}

	static void makeSet(int x) {
		parents[x] = x;
	}

	static int findSet(int x) {
		if (x == parents[x])
			return x;
		else {
			parents[x] = findSet(parents[x]);
			return (int) parents[x];
		}
	}

	static void union(int x, int y) {
		int px = findSet(x);
		int py = findSet(y);
		parents[py] = px;
	}

}

Prim Algorithm1

• 메모리 : 60,320 kb

• 시간 : 466 ms

• 코드길이 : 2,601

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

public class Solution_D4_1251_하나로_Prim {

	static int N;
	static long[][] island;
	static long[][] graph;
	static double E;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder answer = new StringBuilder();
		int T = Integer.parseInt(in.readLine());

		for (int t = 1; t <= T; t++) {
			answer.append("#").append(t).append(" ");
			N = Integer.parseInt(in.readLine());
			island = new long[N][2];

			// X좌표 입력.
			StringTokenizer xLine = new StringTokenizer(in.readLine(), " ");
			// Y좌표 임력.
			StringTokenizer yLine = new StringTokenizer(in.readLine(), " ");
			for (int i = 0; i < N; i++) {
				island[i] = new long[] { Integer.parseInt(xLine.nextToken()), Integer.parseInt(yLine.nextToken()) };
			}
			E = Double.parseDouble(in.readLine());

			// 입력된 자료를 기반으로 섬 간의 가중치 그래프 구하기.
			graph = new long[N][N];
			long[] from, to;
			for (int r = 0; r < N; r++) {
				from = island[r];
				for (int c = r + 1; c < N; c++) {
					to = island[c];
					graph[c][r] = graph[r][c] = (from[0] - to[0]) * (from[0] - to[0])
							+ (from[1] - to[1]) * (from[1] - to[1]);
				}
			}

			double cost = prim(0) * E;
			answer.append(Math.round(cost)).append("\n");

		} // end test-case

		System.out.print(answer);
		in.close();
	}

	private static double prim(int start) {

		// MST에 들어가지 않은 녀석들.
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		// 모든 정점들을 다 관리.
		Edge[] dynamicGraph = new Edge[N];

		for (int n = 0; n < N; n++) {
			dynamicGraph[n] = new Edge(n, Long.MAX_VALUE);
			if (n == start) {
				dynamicGraph[n].cost = 0;
			}
			pq.add(dynamicGraph[n]);
		}
		long cost = 0;

		while (!pq.isEmpty()) {
			Edge front = pq.poll(); // MST에 포함되는 녀석.
			cost += front.cost;

			// 자식 탐색.
			for (int i = 0; i < N; i++) {
				Edge child = dynamicGraph[i];
				// pq : 비MST.
				if (pq.contains(child)) {
					long tempCost = graph[front.idx][child.idx];
					if (tempCost < child.cost) {
						child.cost = tempCost;
						pq.remove(child);
						pq.offer(child);
					}
				}
			}
		}

		return cost;
	}

	static class Edge implements Comparable<Edge> {
		int idx;
		long cost;

		public Edge(int idx, long cost) {
			super();
			this.idx = idx;
			this.cost = cost;
		}

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

	}
}

Prim Algorithm2

• 메모리 : 49,284 KB

• 실행시간 : 251 ms

• 코드길이 : 2,029 B

• 소요시간 : 40M

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

public class Solution_D4_1251_하나로_Prim2 {

	static long[][] island;
	static long[][] graph;
	static int[] parents;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder answer = new StringBuilder();
		int T = Integer.parseInt(in.readLine());

		for (int tc = 1; tc <= T; tc++) {
			answer.append('#').append(tc).append(' ');
			int N = Integer.parseInt(in.readLine());
			island = new long[N][2];
			StringTokenizer stX = new StringTokenizer(in.readLine(), " ");
			StringTokenizer stY = new StringTokenizer(in.readLine(), " ");
			for (int i = 0; i < N; i++) {
				island[i][0] = Long.parseLong(stX.nextToken());
				island[i][1] = Long.parseLong(stY.nextToken());
			}

			double E = Double.parseDouble(in.readLine()); // 입력완료
			graph = new long[N][N];
			for (int i = 0; i < N - 1; i++) {
				for (int j = i + 1; j < N; j++) {
					graph[i][j] = graph[j][i] = (long) (Math.pow(island[i][0] - island[j][0], 2)
							+ Math.pow(island[i][1] - island[j][1], 2));
				}
			}

			boolean[] check = new boolean[N];
			long[] key = new long[N];
			int[] p = new int[N];

			Arrays.fill(key, Long.MAX_VALUE);

			p[0] = -1;
			key[0] = 0;

			for (int i = 0; i < N - 1; i++) {
				long min = Long.MAX_VALUE;
				int index = -1;
				for (int j = 0; j < N; j++) {
					if (!check[j] && key[j] < min) {
						index = j;
						min = key[j];
					}
				}

				check[index] = true;
				for (int j = 0; j < N; j++) {
					if (!check[j] && graph[index][j] > 0 && key[j] > graph[index][j]) {
						p[j] = index;
						key[j] = graph[index][j];
					}
				}
			}
			double result = 0;
			for (int i = 0; i < N; i++) {
				result += key[i];
			}
			result *= E;
			answer.append(Math.round(result)).append('\n');
		} // end test-case

		System.out.print(answer);
		in.close();
	}
}