[SWEA JAVA] 1251. [S/W 문제해결 응용] 4일차 - 하나로

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

SW Expert Academy

 

1. 크루스칼로 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Solution {
	public static int T, V, cnt = 0;
	public static long ans = 0;
	public static int[] p, size, X, Y, arr;
	public static double E, Min = 0;
	public static List<Line> list;
	
	public static class Line {
		int from, to;
		double value;

		public Line(int from, int to, double value) {
			super();
			this.from = from;
			this.to = to;
			this.value = value;
		}

	}

	public static void make() {
		for (int i = 0; i < V; i++) {
			p[i] = i;
		}
	}

	public static boolean Union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if (aRoot == bRoot)
			return false;
		if (size[aRoot] > size[bRoot])
			p[bRoot] = aRoot;
		else if (size[aRoot] == size[bRoot])
			size[bRoot]++;

		if (size[bRoot] > size[aRoot]) {
			p[aRoot] = bRoot;
		}
		return true;
	}

	public static int findSet(int a) {
		if (a == p[a])
			return a;
		p[a] = findSet(p[a]);
		return p[a];
	}

	public static int check(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if (aRoot == bRoot)
			return 1;
		else
			return 0;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			// 1.입력받기
			V = Integer.parseInt(br.readLine());
			
			p = new int[V];
			size = new int[V];
			X = new int[V];
			Y = new int[V];
			arr = new int[2];
			list = new ArrayList<>();
			make();
			
			// 1-1. X, Y 입력받기
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < V; i++) {
				X[i] = Integer.parseInt(st.nextToken());
			}
			
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < V; i++) {
				
				Y[i] = Integer.parseInt(st.nextToken());
			}
			
			E = Double.parseDouble((br.readLine()));
			
			// 2. 간선 만들기 조합 
			dfs(0, 0);

			// 3. 크루스칼
			
			list.sort((o1, o2) -> Double.compare(o1.value, o2.value));
			
			cnt = 0;
			Min = 0;
			ans = 0;
			
			for (int i = 0; i < (V * (V-1)) / 2; i++) {

				Line cur = list.get(i);
				if (Union(cur.from, cur.to)) { // Union가능하다면
					cnt++;
					Min += cur.value * E;
				}

				if (cnt == V - 1)
					break;
			}
			// 4. 출력
			ans = (long)Math.round(Min);
			System.out.println("#" + tc + " " + ans);
		}

	}

	public static void dfs(int at, int depth) {
		if(depth == 2) {
			long dx = Math.abs(X[arr[0]] - X[arr[1]]);
			long dy = Math.abs(Y[arr[0]] - Y[arr[1]]);
			double value = (dx * dx) + (dy * dy);
			list.add(new Line(arr[0], arr[1], value));
			
			return;
		}
		for(int i =at;i<V;i++) {
			arr[depth] = i;
			dfs(i+1, depth+1);
		}
	}
}

 

2. 프림으로 풀이

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

public class Main {
	public static int T, V;
	public static int[] X, Y, arr;
	public static long ans = 0;
	public static double E, Min = 0;
	public static double[][] adjMatrix;
	public static boolean[] visited;
	
	public static class Edge implements Comparable<Edge> {
		int w;
		double cost;

		public Edge(int w, double cost) {
			super();
			this.w = w;
			this.cost = cost;
		}

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			V = Integer.parseInt(br.readLine()); // 정점 수
			adjMatrix = new double[V][V];
			visited = new boolean[V]; // 방문여부 배열 (트리 포함정점배열)
			X = new int[V];
			Y = new int[V];
			arr = new int[2];
			
			// 1-1. X, Y 입력받기
			st = new StringTokenizer(br.readLine());
			for(int i =0;i<V;i++) {
				X[i] = Integer.parseInt(st.nextToken());
			}
			
			st = new StringTokenizer(br.readLine());
			for(int i =0;i<V;i++) {
				Y[i] = Integer.parseInt(st.nextToken());
			}
			
			E = Double.parseDouble(br.readLine());
			
			// 2. 정점 별 거리 구하기 조합
			dfs(0, 0);
			
			
			// 3. 프림
			Min = 0;

			PriorityQueue<Edge> q = new PriorityQueue<>(); // 자신과 타정점들간의 간선비용 중 최소 간선 비용
			q.offer(new Edge(0, 0));// 0번 정점을 트리의 시작 정점이 되도록 함 (다른 정점이어도 상관없음)

			while (!q.isEmpty()) {
				// step1 : 트리 구성에 포함된 가장 유리한 정점 선택( 비트리 정점 중 최소비용 간선의 정점 선택 )
				Edge edge = q.poll();
				int v = edge.w;
				double cost = edge.cost;

				// step2 : 선택된 정점과 타 정점들 간선비용 비교하기
				if (visited[v])
					continue;

				visited[v] = true;
				Min += cost;

				for (int i = 0; i < V; i++) {
					if (!visited[i] && adjMatrix[v][i] != 0) {
						q.offer(new Edge(i, adjMatrix[v][i]));
					}
				}

			}
			
			
			// 4. 출력
			ans = (long)Math.round(Min *E);
			System.out.println("#" + tc + " " + ans);
		}

	}

	public static void dfs(int at, int depth) {
		if(depth == 2) {
			long dx =  Math.abs(X[arr[0]] - X[arr[1]]);
			long dy =  Math.abs(Y[arr[0]] - Y[arr[1]]);
			double value = (dx * dx) + (dy * dy);
			adjMatrix[arr[0]][arr[1]] = value;
			adjMatrix[arr[1]][arr[0]] = value;
			
			return;
		}
		for(int i = at ;i<V; i++) {
			arr[depth] = i;
			dfs(i+1, depth+1);
		}
	}
}

 

 

마찬가지로 값 범위에 주의 연산할때 넘어갈수도 있다.

 

long dx = Math.abs(X[arr[0]] - X[arr[1]]);
long dy = Math.abs(Y[arr[0]] - Y[arr[1]]);
double value = (dx * dx) + (dy * dy);

 

위에 long 부분을 int로 바꾸면 오버플로우가 일어난다. x의 범위가 백만인데 value에 저장할때 dx * dx 를 int에서 연산하면 20억이 넘어가기 때문 (1조)

 

간선의 수가 많기 때문에 정점 중심의 알고리즘인 프림 알고리즘이 실행시간에 있어서 더 유리할것이라 생각했지만 오히려 크루스칼 알고리즘이 실행시간이 300ms정도 빨랐다.