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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD&categoryId=AV15StKqAQkCFAYD&categoryType=CODE

SW Expert Academy

---

• Kruskal

import java.util.Arrays;
import java.util.Scanner;

public class Solution {
	static class Edges implements Comparable<Edges> {
		int v1;
		int v2;
		long cost;
		public Edges(int v1, int v2, long cost) {
			this.v1=v1;
			this.v2=v2;
			this.cost=cost;
		}
		
		@Override
		public int compareTo(Edges o) {
			return Long.compare(this.cost, o.cost);
		}
	}
	static int[] parents;
	static int[] rank;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for(int tc=1; tc<=T; tc++) {
			// 정점의 개수 
			int N = sc.nextInt();
			// N개의 x, y좌표를 입력받아서 저장해둘 배열
			int[][] arr = new int[N][2];
			// x좌표
			for(int i=0; i<N; i++) arr[i][0] = sc.nextInt();
			// y좌표
			for(int i=0; i<N; i++) arr[i][1] = sc.nextInt();
			// 세금
			double E = sc.nextDouble();
			
			// 정점1 정점2 가중치
			Edges[] edges = new Edges[N*(N-1)/2];
			int cnt = 0;
			for(int i=0; i<N-1; i++) {
				for(int j=i+1; j<N; j++) {
					edges[cnt] = new Edges(i, j, dist(arr[i][0], arr[j][0], arr[i][1], arr[j][1]));
					cnt++;
				}
			}
		
			// 정렬
			Arrays.sort(edges);
			
			// union find 연산을 위한 준비
			parents = new int[N];
			rank = new int[N];
			for(int i=0; i<N; i++) makeSet(i);
			
			// 크루스칼 동작
			long result = 0;
			cnt = 0;
			for(int i=0; i<(N*(N-1)/2); i++) {
				int v1 = findSet(edges[i].v1);
				int v2 = findSet(edges[i].v2);
				if(v1==v2) continue;
				result += edges[i].cost;
				union(v1, v2);
				cnt++;
				if(cnt==N-1) break;
			}
			System.out.println("#" + tc + " " + Math.round(result*E));
		}
	}
	
	static long dist(int x1, int x2, int y1, int y2) {
		return (long)(Math.pow(x1-x2,  2) + Math.pow(y1-y2, 2));
	}
	
	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 findSet(parents[x]);
		}
	}
	
	static void union(int x, int y) {
		int px = findSet(x);
		int py = findSet(y);
		if( rank[px] > rank[py] ) {
			parents[py] = px;
		} else {
			parents[px] =py;
			if(rank[px] == rank[py]) {
				rank[py]++;
			}
		}
	}
}

---

• Prim

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Solution {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			int N = sc.nextInt();
			// 각 정점별로 인접리스트 참조변수
			long[][] adj = new long[N][N];
			int[][] arr = new int[N][2];
			for (int i = 0; i < N; i++)
				arr[i][0] = sc.nextInt();
			for (int i = 0; i < N; i++)
				arr[i][1] = sc.nextInt();
			double E = sc.nextDouble();
			// 입력되어지는 간선 배열을 인접리스트에 저장
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					long c = distance(arr[i][0], arr[j][0], arr[i][1], arr[j][1]);
					adj[i][j] = c;
					adj[j][i] = c;
				}
			}
			boolean[] visited = new boolean[N];
			long[] dist = new long[N];
			Arrays.fill(dist, Long.MAX_VALUE);
			long result = 0, min = 0;
			dist[0] = 0;
			int index;
			// 시작정점을 뺀 나머지 정점 수 만큼 반복
			for (int i = 0; i < N - 1; i++) {
				min = Long.MAX_VALUE;
				index = -1;
				// 아직 안고른 친구중에 젤 거리값이 작은 친구
				for (int j = 0; j < N; j++) {
					if (!visited[j] && dist[j] < min) {
						min = dist[j];
						index = j;
					}
				}
				for (int j = 0; j < N; j++) {
					if (!visited[j] && adj[index][j] != 0 && dist[j] > adj[index][j]) {
						dist[j] = adj[index][j];
					}
				}
				visited[index] = true;
			}
			for (int i = 0; i < N; i++)
				result += dist[i];
			System.out.println("#" + tc + " " + Math.round(result * E));
		}
	}

	static long distance(int x1, int x2, int y1, int y2) {
		long d = (long) ((Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2)));
		return d;
	}
}