SWEA 1238 - 하나로

Java

1238 번 - 하나로

문제

n개의 섬이 있으며, 각 섬을 이어 모든 섬을 오갈 수 있게 해야한다.
섬을 잇는 비용은 환경 부담 세율(E)과 각 해저터널 길이(L)의 제곱의 곱(E * L^2) 이다.

섬을 잇는 최소 비용은?

접근 방법

우선 섬과 섬을 잇는 모든 비용을 2차원 배열을 통해 구하였다.
이후 간선을 잇는 최소 비용을 구하는 문제이므로, Prim 알고리즘을 사용하여 해결하였다.

코드

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

class Solution {
	static int n;
	static double[][] island;
	static double e, result;
	static int[] x,y;
	public static void main(String []args) throws Exception {  
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	int tc = stoi(br.readLine());
    	
    	for(int tidx = 1; tidx <= tc; tidx++) {
    		result = 0;
    		n = stoi(br.readLine());
    		island = new double[n][n];
    		x = new int[n];
    		y = new int[n];
    		
    		stk = new StringTokenizer(br.readLine());
    		for(int i = 0; i < n; i++) {
    			x[i] = stoi(stk.nextToken());
    		}
    		stk = new StringTokenizer(br.readLine());
    		for(int i = 0; i < n; i++) {
    			y[i] = stoi(stk.nextToken());
    		}
    		e = Double.parseDouble(br.readLine());
    		// 섬을 잇는 모든 비용을 계산한다.
    		for(int i = 0; i < n; i++) {
    			for(int j = 0; j < n; j++) {
    				if(i == j)
    					continue;
    				island[i][j] = (Math.pow(x[i] - x[j], 2) + Math.pow(y[i] - y[j], 2)) * e;
    			}
    		}
    		
    		// prim 알고리즘
    		boolean vis[] = new boolean[n];
    		double[] minEdge = new double[n];
    		Arrays.fill(minEdge, Double.MAX_VALUE);	// 가장 최소의 간선을 찾아야 하므로, 초기 값은 Max
    		
    		minEdge[0] = 0;		// 첫 시작 점은 0으로 한다.
    		int minVertex = 0;

    		for(int c = 0; c < n; c++) {
    			double min = Double.MAX_VALUE;
    			
    			for(int i = 0; i < n; i++) {
    				if(!vis[i] && min > minEdge[i]) {		// 현재 저장 된 간선 중에 가장 값이 적은 간선을 선택한다. 처음은 0이 선택된다.
    					min = minEdge[i];	
    					minVertex = i;		// 그것과 연결 된 vertex
    				}
    			}
    			
    			result += min;
    			vis[minVertex] = true;		
    			
    			for(int i = 0; i < n; i++) {	
					// 현재 vertex와 연결된 간선들과 이전 vertex와 연결 되었던 간선들의 값을 비교한다. 
					// 이전 vertex의 연결된 간선의 비용보다 현재 vertex에 연결하는 간선의 비용이 더 작다면 갱신한다.
    				if(!vis[i] && island[minVertex][i] != 0 && minEdge[i] > island[minVertex][i]) {
    					minEdge[i] = island[minVertex][i];
    				}
    			}
    		}

    		long result_l = Math.round(result);
    		System.out.println("#" + tidx + " " + result_l);
    	}
    	
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

코드 - Priority Queue

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

class Solution {
	static class Node implements Comparable<Node> {
		int end;			// 현재 정과 연결 되어 있는 끝 정점
		double weight;			// 가중치
		
		public Node(int end, double weight) {
			this.end = end;
			this.weight = weight;
		}
		@Override
		public int compareTo(Node o) {
			return Double.compare(weight,o.weight);
		}
	}
	static int n;
	static List<List<Node>> island;
	static double e, result;
	static int[] x,y;
	public static void main(String []args) throws Exception {  
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	int tc = stoi(br.readLine());
    	
    	for(int tidx = 1; tidx <= tc; tidx++) {
    		result = 0;
    		n = stoi(br.readLine());
    		island = new ArrayList<List<Node>>();
    		for(int i = 0; i < n; i++) {
    			island.add(new ArrayList<Node>());
    		}
    		
    		x = new int[n];
    		y = new int[n];
    		
    		stk = new StringTokenizer(br.readLine());
    		for(int i = 0; i < n; i++) {
    			x[i] = stoi(stk.nextToken());
    		}
    		stk = new StringTokenizer(br.readLine());
    		for(int i = 0; i < n; i++) {
    			y[i] = stoi(stk.nextToken());
    		}
    		e = Double.parseDouble(br.readLine());
    		
    		for(int i = 0; i < n; i++) {
    			for(int j = 0; j < n; j++) {
    				if(i == j)
    					continue;
    				island.get(i).add(new Node(j, (Math.pow(x[i] - x[j], 2) + Math.pow(y[i] - y[j], 2)) * e));
    			}
    		}
    		
    		// prim 알고리즘
    		boolean vis[] = new boolean[n];
    		double[] minEdge = new double[n];
    		Arrays.fill(minEdge, Double.MAX_VALUE);
    		int minVertex = 0;
    		minEdge[0] = 0;
    		
    		PriorityQueue<Node> queue = new PriorityQueue<>();
    		queue.add(new Node(0,0));
    		
    		while(!queue.isEmpty()) {
    			double min = Double.MAX_VALUE;
    			
    			Node curNode = queue.poll();
    			int curN = curNode.end;
    			if(vis[curN]) continue;
    			vis[curN] = true;
    			
    			result += curNode.weight;
    			
    			for(Node list : island.get(curN)) {
    				if(minEdge[list.end] > list.weight) {
    					minEdge[list.end] = list.weight;
    					queue.add(new Node(list.end, minEdge[list.end]));
    				}
    			}
    			
    		}
    		long result_l = Math.round(result);
    		System.out.println("#" + tidx + " " + result_l);
    	}
    	
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐★★★

후기

prim, kruscal, dijkstra를 공부해야한다.

개선할 점

없