[SWEA]1251_하나로 (크루스칼)

문제를 읽으면 전체 섬들을 다 합치는거다. 그럼 최소신장트리를 이용한 문제란 감이 온다.

근데 좀 짜증나는게 입력값으로 x좌표 따로, y좌표 따로 온다. 아니 이건 인접리스트를 만들어야 되나 인접행렬을 만들어야되나고민이 됐다.

다시 정리해보면,

[알고리즘]최소신장트리(크루스칼,프림)

-인접리스트로 만들어서 푸는거 = 크루스칼

크루스칼 장점 : 좀 더 구현하기 수월함

단점 : 간선들을 정렬해줘야 해서 시간이 쪼오금 더 걸림

 

-인접행렬로 만들어서 푸는거 = 프림.

 

암튼, 이렇게 짱나게 입력값이 오는데, 걍 x들은 xArr[]배열에다가 때려박고, y들은 yArr[]에 때려박았다.

글고나서 각각 점들의 거리를 하나하나 다~구해서 Edge라는 클래스를 만들어서 놓고 얘를 PQ에 넣는다

static class Edge implements Comparable<Edge>{
		int from;
		int to;
		double dist;
		
		public Edge(int from, int to, double dist) {
			super();
			this.from = from;
			this.to = to;
			this.dist = dist;
		}
		
		@Override
		public int compareTo(Edge o) {
			return (int)(this.dist - o.dist);
		}
		
	}

//모든 간선들의 길이 구해서 pq에 넣기
			PriorityQueue<Edge> pq = new PriorityQueue<>();
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					double disX = Math.pow((xArr[i]-xArr[j]), 2);
					double disY = Math.pow((yArr[i]-yArr[j]), 2);
					double dis = disX + disY;
					pq.offer(new Edge(i,j,dis));
				}
			}

 

그담엔 크루스칼! 하면 바로 떠올리는 함수들: union, findSet, makeSet을 활용한 로직을 실행해주면 된다.

	static void makeSet() {
		for(int i=0; i<N; i++) {
			parents[i] = i;
  		}
	}
	
	static int findSet(int a) {
		if(a == parents[a]) return a;
		return parents[a] = findSet(parents[a]);
	}
	
	static boolean union(int a, int b) {
		int rootA = findSet(a);
		int rootB = findSet(b);
		if(rootA==rootB) return false;
		parents[rootB] = rootA;
		return true;
	}

아래에서 union을 써먹기 위해 위에서 static 함수를 따로 구성해줌

                    double cost = 0;
                    while(!pq.isEmpty()) {
                        Edge e =pq.poll();
                        if(union(e.from, e.to)) {
                            cost+= E * e.dist;
                        }
                    }

 

전체 코드:

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

public class SWEA1251하나로 {

	//최소신장트리
	static class Edge implements Comparable<Edge>{
		int from;
		int to;
		double dist;
		
		public Edge(int from, int to, double dist) {
			super();
			this.from = from;
			this.to = to;
			this.dist = dist;
		}
		
		@Override
		public int compareTo(Edge o) {
			return (int)(this.dist - o.dist);
		}
		
	}
	static void makeSet() {
		for(int i=0; i<N; i++) {
			parents[i] = i;
  		}
	}
	
	static int findSet(int a) {
		if(a == parents[a]) return a;
		return parents[a] = findSet(parents[a]);
	}
	
	static boolean union(int a, int b) {
		int rootA = findSet(a);
		int rootB = findSet(b);
		if(rootA==rootB) return false;
		parents[rootB] = rootA;
		return true;
	}
	
	static int[] parents;
	static int N;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			double[] xArr = new double[N];
			double[] yArr = new double[N];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int i=0; i<N; i++) {
				xArr[i] = Double.parseDouble(st.nextToken());
			}
			st = new StringTokenizer(br.readLine());
			for(int i=0; i<N; i++) {
				yArr[i] = Double.parseDouble(st.nextToken());
			}
			double E = Double.parseDouble(br.readLine());
			//..입력끝
			
			parents = new int[N];
			
			makeSet();
			
			//모든 간선들의 길이 구해서 pq에 넣기
			PriorityQueue<Edge> pq = new PriorityQueue<>();
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					double disX = Math.pow((xArr[i]-xArr[j]), 2);
					double disY = Math.pow((yArr[i]-yArr[j]), 2);
					double dis = disX + disY;
					pq.offer(new Edge(i,j,dis));
				}
			}
			
			double cost = 0;
			while(!pq.isEmpty()) {
				Edge e =pq.poll();
				if(union(e.from, e.to)) {
					cost+= E * e.dist;
				}
			}
			Long ans = Math.round(cost);
			sb.append("#").append(tc).append(" ").append(ans).append("\n");
		}
		System.out.print(sb.toString());
	}
}

 

 

문제:

당신은 인도네시아 내의 N개의 섬들을 연결하는 교통시스템 설계 프로젝트인 ‘하나로’를 진행하게 되었습니다.

하나로 프로젝트는 천해의 자연을 가진 인도네시아의 각 섬 간 교통이 원활하지 않아 관광 산업의 발전을 저해하는 요소를 줄이고 부가 가치를 창출하고자 진행하는 프로젝트입니다.

본 프로젝트에서는 인도네시아 내의 모든 섬을 해저터널로 연결하는 것을 목표로 합니다.

해저터널은 반드시 두 섬을 선분으로 연결하며, 두 해저 터널이 교차된다 하더라도 물리적으로는 연결되지 않는 것으로 가정합니다.

아래 그림 1과 같은 경우, A섬에서 D섬으로는 연결되었지만 A섬으로부터 B섬, C섬에는 도달 할 수 없기 때문에 연결되지 않은 것입니다.

 

 
다음 두 가지의 경우는 모든 섬이 연결된 것입니다.
 

 

위와 같은 방법을 통해 인도네시아 내의 모든 섬들을 연결해야 하는 프로젝트입니다.

그림 3에서 B와 A처럼 직접적으로 연결된 경우도 있지만, B와 C처럼 여러 섬에 걸쳐 간접적으로 연결된 경우도 있습니다.

다만 인도네시아에서는 해저터널 건설로 인해 파괴되는 자연을 위해 다음과 같은 환경 부담금 정책이 있습니다.

- 환경 부담 세율(E)과 각 해저터널 길이(L)의 제곱의 곱(E * L^2)만큼 지불

총 환경 부담금을 최소로 지불하며, N개의 모든 섬을 연결할 수 있는 교통 시스템을 설계하시오.

64비트 integer 및 double로 처리하지 않을 경우, overflow가 발생할 수 있습니다 (C/C++ 에서 64비트 integer는 long long 으로 선언).

위의 그림 2은 환경 부담금을 최소로 하며 모든 섬을 연결하고 있지만, 그림 3는 그렇지 않음을 알 수 있습니다.

[입력]

가장 첫 줄은 전체 테스트 케이스의 수이다.

각 테스트 케이스의 첫 줄에는 섬의 개수 N이 주어지고 (1≤N≤1,000),

두 번째 줄에는 각 섬들의 정수인 X좌표, 세 번째 줄에는 각 섬들의 정수인 Y좌표가 주어진다 (0≤X≤1,000,000, 0≤Y≤1,000,000).

마지막으로, 해저터널 건설의 환경 부담 세율 실수 E가 주어진다 (0≤E≤1).

[출력]

각 테스트 케이스의 답을 순서대로 출력하며, 각 케이스마다 줄의 시작에 “#C”를 출력하여야 한다. 이때 C는 케이스의 번호이다.

같은 줄에 빈칸을 하나 두고, 주어진 입력에서 모든 섬들을 잇는 최소 환경 부담금을 소수 첫째 자리에서 반올림하여 정수 형태로 출력하라.