SWEA_1251 하나로(자바) / 최소신장트리

문제 링크

SW Expert Academy

이 문제는 각각의 섬들이 연결이 되어야 하는 문제입니다.

 

N개의 섬들이 완전연결이 될 필요는 없지만, 다른 섬을 통해서 모든 섬에 갈 수 있어야 합니다.

 

이때 터널을 연결하는 비용은 각 좌표의 길이 값입니다. 

 

길이의 값은 피타고라스의 정리를 이용해서 구할 수 있습니다. -> a^2 + b^2 = c^2

 

가격은 C^2를 내야 한다니까, 조금의 수고는 덜은거 같습니다.

 

이때의 최소 부담금을 구하는 문제입니다.

 

최소 신장 트리를 이용해서 문제풀이를 진행했습니다.

 

정점을 섬의 갯수, 간선을 해저터널로 볼 수 있습니다.

 

알고리즘은 정점을 중심으로 푸는 PRIM알고리즘과

 

간선을 중심으로 푸는 Kruskal로 풀이를 진행할 수 있습니다.

 

Prim을 이용한 문제풀이

package com.Expert;

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


public class Expert_1251 {
	private static int N;
	private static long[][] adjMatrix;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCase = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc <= testCase; tc++) {
			N = Integer.parseInt(br.readLine());
			adjMatrix = new long[N][N];

			int x[] = new int[N];
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			for (int i = 0; i < N; i++) {
				x[i] = Integer.parseInt(st.nextToken());
			}

			int y[] = new int[N];
			for (int i = 0; i < N; i++) {
				y[i] = Integer.parseInt(st.nextToken());
			}
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					adjMatrix[i][j]= adjMatrix[j][i]
                    = getDistance(x[i], x[j], y[i], y[j]);
				}
			}
			double E = Double.parseDouble(br.readLine());
			System.out.println("#"+tc+" "+Math.round(makeMST()*E));
		}
	}
	private static long makeMST() {
		long [] minEdge = new long[N];
		boolean[] visited = new boolean[N];
		
		Arrays.fill(minEdge, Long.MAX_VALUE);
		
		minEdge[0] = 0;
		
		long result = 0; //최소신장트리 비용
		int cnt = 0; // 정점 개수
		
		while(true) {
			long min = Long.MAX_VALUE;
			int minNo =0;
			for (int i = 0; i < N; i++) {
				if(!visited[i] && min>minEdge[i]) {
					minNo = i;
					min = minEdge[i];
				}
			}
			
			visited[minNo] = true;
			result += min;
			if(++cnt ==N) break;
			
			for (int i = 0; i < N; i++) {
				if(!visited[i] && minEdge[i] > adjMatrix[minNo][i] ) {
					minEdge[i] = adjMatrix[minNo][i];
				}
			}
		}
		return result;
	}
	static long getDistance(int x1,int x2,int y1,int y2) {
		return (long)(Math.pow(x1-x2, 2)+Math.pow(y1-y2,2));
	}
	
}

 

Prim을 이용해서 푸는 경우에도 우선순위 큐를 적용해서 문제풀이도 가능합니다.

 

Prim+우선순위 큐를 이용해서 문제를 풀이한 경우

package com.Expert;

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


public class Expert_1251 {
	private static int N;
	private static long[][] adjMatrix;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCase = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc <= testCase; tc++) {
			N = Integer.parseInt(br.readLine());
			adjMatrix = new long[N][N];

			int x[] = new int[N];
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			for (int i = 0; i < N; i++) {
				x[i] = Integer.parseInt(st.nextToken());
			}

			int y[] = new int[N];
			for (int i = 0; i < N; i++) {
				y[i] = Integer.parseInt(st.nextToken());
			}
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					adjMatrix[i][j]= adjMatrix[j][i] 
                    = getDistance(x[i], x[j], y[i], y[j]);
				}
			}
			double E = Double.parseDouble(br.readLine());
			System.out.println("#"+tc+" "+Math.round(makeMST()*E));
		}
	}
	private static long makeMST() {
		long [] minEdge = new long[N];
		boolean[] visited = new boolean[N];
		
		Arrays.fill(minEdge, Long.MAX_VALUE);

		minEdge[0] = 0;
		
		PriorityQueue<Vertex> queue = new PriorityQueue<>();
		queue.offer(new Vertex(0, minEdge[0]));
		
		long result = 0; 
		int cnt = 0;
		
		while(true) {
			ertex minVertex = queue.poll();
			if(visited[minVertex.no]) continue;
			
			visited[minVertex.no] = true;
			result += minVertex.cost;
			if(++cnt ==N) break;
			
			for (int i = 0; i < N; i++) {
				if(!visited[i] && minEdge[i] > adjMatrix[minVertex.no][i] ) {
					minEdge[i] = adjMatrix[minVertex.no][i];
					queue.offer(new Vertex(i,minEdge[i]));
				}
			}
		}
		return result;
	}
	static long getDistance(int x1,int x2,int y1,int y2) {
		return (long)(Math.pow(x1-x2, 2)+Math.pow(y1-y2,2));
	}
	static class Vertex implements Comparable<Vertex>{
		int no;
		long cost;
		
		public Vertex(int no, long cost) {
			super();
			this.no = no;
			this.cost = cost;
		}

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