하나로 [SWEA 1251][Java][프림][크루스칼]

[광고 누르면 오늘의 행운 상승!!]

 

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AW--k1o64VwDFAVg&contestProbId=AV15StKqAQkCFAYD&probBoxId=AXDDfV4KYwgDFAVX+&type=PROBLEM&problemBoxTitle=20200311&problemBoxCnt=++1+

 

SW Expert Academy

문제의 저작권은 SW Expert Academy에 있습니다.

프림 알고리즘 이란?

- 프림 알고리즘은 MST(최소신장트리)를 구현하는 한 방법으로 다익스트라(Dijkstra) 알고리즘과 유사하게 동작한다.

- 트리에 연결되지 않은 정점들은 큐에 add되어 있다.

- 각 정점들은인접한 정점 중 최소 비용으로 이동가능한 정점을 선택하여 추가한다.

1. type을 int로 하면 오버플로우가 발생한다. long과 double을 이용한다.

2. 한 정점에서 시작하여 인접한 정점을 잇는 간선 중 가중치가 가장 낮은 간선을 선택한다.

3. 정점들이 이어져 있는 간선들을 반복해서 비교하며 가중치가 가장 낮은 간선을 추가한다.

4. 모든 요소가 이어졌다면 총 COST를 반환한다.

5. math.pow와 math.round를 활용하여 제곱과 반올림을 사용했다.

package Study0307;


import java.io.*;
import java.util.*;

public class 하나로2 {
	public 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 String toString() {
			// TODO Auto-generated method stub
			return super.toString();
		}
		@Override
		public int compareTo(Edge o) {
			// o.cost - Long.MIN_VALUE 범위초과
			//return this.cost - o.cost > 0 ? 1 : -1; //거리가 작은 것 부터
			return Long.compare(this.cost, o.cost);
		}
	}
	public static int N,ans;
	public static double E;
	public static long graph[][];
	public static List<Integer> X;
	public static List<Integer> Y;
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		
		for (int tc = 1; tc <= T; tc++) {
			st = read(br);
			N = Integer.parseInt(st.nextToken());
			
			X = new ArrayList<>();
			Y = new ArrayList<>();
			
			StringTokenizer stX = read(br);
			StringTokenizer stY = read(br);
			
			for (int i = 0; i < N; i++) {
				X.add(Integer.parseInt(stX.nextToken()));
				Y.add(Integer.parseInt(stY.nextToken()));
			}
				
			st = read(br);
			E = Double.parseDouble(st.nextToken());
			
			graph = new long[N][N];
			int[] from, to;
			for (int r = 0; r < N; r++) {
				long x1 = X.get(r);
				long y1 = Y.get(r);
				for (int c = r+1; c < N; c++) {
					long x2 = X.get(c);
					long y2 = Y.get(c);
					
					graph[c][r] = graph[r][c] = 
							(long)(Math.pow(x1-x2, 2) +Math.pow(y1-y2, 2));
				}
			}
			double cost = Prim(0) * E;
			System.out.println("#" + tc + " " + Math.round(cost));
		}
	}
	private static double Prim(int start) {
		
		// MST에 들어가지 않은 녀석들..
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		//모든 정점들을 다 관리....
		Edge[] dynamicGraph = new Edge[N];
		
		for (int n = 0; n < dynamicGraph.length; n++) {
			dynamicGraph[n] = new Edge(n,Long.MAX_VALUE);
			if(n==start) {
				dynamicGraph[start].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 < dynamicGraph.length; i++) {
				Edge child = dynamicGraph[i];
				//MST에 포함되어있지 않다.
				if(pq.contains(child)) {
					//pq : 비 MST
					long tempCost = graph[front.idx][child.idx];
					if(tempCost < child.cost) {
						child.cost = tempCost;
						//순서 재정립
						pq.remove(child);
						pq.add(child);
					}
				}
			}
		}
		
		return cost;
	}
	
	private static StringTokenizer read(BufferedReader br) throws IOException {
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		return st;
	}
}

크루스칼 알고리즘 이란?

탐욕적인 방법(greedy method) 을 이용하여 그래프의 모든
정점을 최소 비용으로 연결하는 최소 비용을 구하는 것이다.

1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.

2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.

3. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다.

<<UnionFind 를 이용하여 서로 다른 집합이면서 사이클이 형성되지 않는다면 
간선을 추가하고 같은 집합으로 만든다.>>

package Study3;

import java.io.*;
import java.util.*;

public class 하나로 {
	public static class Edge implements Comparable<Edge>{
		int x,y;
		double distance;
		Edge(int x, int y, double distance){
			this.x = x;
			this.y = y;
			this.distance = distance;
		}
		@Override
		public int compareTo(Edge o) {
			return Double.compare(distance, o.distance); //거리가 작은 것 부터
		}
	}
	public static void union(int[] p , int x, int y) {
		x= findSet(p, x);
		y= findSet(p, y);
		if(x>y) p[y] = x;
		else p[x] = y; // 그냥 우리가 정했어요~! 작은값을 parent로 
	}
	public static boolean find(int[] p , int x, int y) {
		return findSet(p, x) == findSet(p, y);

	}
	public static int findSet(int[] p, int x){ 
		if(x == p[x]) return x;
		return p[x] = findSet(p,p[x]); //이것을 넣고 안 넣고가 퍼포먼스의 큰 차이를 부른다.
	}
	public static int N,ans;
	public static double E;
	public static List<Edge> g;
	public static List<Integer> X;
	public static List<Integer> Y;
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		
		for (int tc = 1; tc <= T; tc++) {
			st = read(br);
			N = Integer.parseInt(st.nextToken());
			
			X = new ArrayList<>();
			Y = new ArrayList<>();
			g = new ArrayList<>();
			
			st = read(br);
			while(st.hasMoreTokens()) {
				//X 좌료 입력
				X.add(Integer.parseInt(st.nextToken()));
			}
			st = read(br);
			while(st.hasMoreTokens()) {
				//Y 좌표 입력
				Y.add(Integer.parseInt(st.nextToken()));
			}
			st = read(br);
			//환경부담금
			E = Double.parseDouble(st.nextToken());
			
			//모든 간선을 가중치를 계산하여 연결한다.
			for (int i = 0; i < N; i++) {
				long x1 = X.get(i);
				long y1 = Y.get(i);
				
				for (int j = i; j < N; j++) {
					if(i==j) continue;
					long x2 = X.get(j);
					long y2 = Y.get(j);
					double d = Math.pow(x2-x1,2) + Math.pow(y2-y1,2);
					double dis = E*d;
					g.add(new Edge(i, j, dis));
				}
			}
			
			Collections.sort(g);
			
			int[] p = new int[N+1]; //정점의 개수만큼 배열 생성
			for(int i = 1; i <= N; i++) p[i] = i;
			
			double sum = 0;
			//간선의 갯수만큼
			for (int i = 0; i < g.size(); i++) {
				if(!find(p,g.get(i).x, g.get(i).y)) { //x의 부모와 y의 부모가 다르면 서로 다른 집합.
					//가중치(거리) 를 더해준다.
					sum += g.get(i).distance;
					//두 집합을 하나의 집합으로 만든다.
					union(p, g.get(i).x, g.get(i).y);
				}
			}
			System.out.println("#" + tc + " " + Math.round(sum));
		}
	}
	private static StringTokenizer read(BufferedReader br) throws IOException {
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		return st;
	}
}

그래프의 간선들을 가중치의 오름차순으로 정렬한다.
정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
즉, 가장 낮은 가중치를 먼저 선택한다.
사이클을 형성하는 간선을 제외한다.
해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다.
https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html