1251. 하나로

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD 

SW Expert Academy

 

분류

그래프 탐색

트리

 

개인적 난이도

매우 쉬움

쉬움

보통

어려움

매우 어려움

 

핵심 알고리즘

각 섬들에 대해 이을 수 있는 모든 간선을 비용과 함게 최소 힙에 넣는다.

최소 힙에서 간선들을 저렴한 순서대로 하나씩 빼며 두 섬을 잇는다.

이 때 간선들이 사이클 구조를 이루지 않도록 하여야 한다.

사이클 구조 없이 N-1개의 간선을 연결하게 되면 반드시 N개의 섬은 이어진다.

 

사이클 구조를 피하기 위해서는 섬들의 부모섬(?)들을 기록해가며

이으려는 두 섬의 부모섬이 같은 경우 해당 간선은 버려야 한다.

 

그러므로 두 섬을 이을 때 섬의 부모를 잘 기록해 두어야 한다.

 

시행착오

없음

 

코드

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

class Solution{
	static Map<Long, Integer> cache;

	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for(int tc = 1; tc <= T; ++tc){
			int N = Integer.parseInt(br.readLine());
			int[] x = new int[N];
			int[] y = new int[N];
			String[] arr_x = br.readLine().split(" ");
			String[] arr_y = br.readLine().split(" ");
			double E = Double.parseDouble(br.readLine());

			for (int i = 0; i < N; i++){
				x[i] = Integer.parseInt(arr_x[i]);
				y[i] = Integer.parseInt(arr_y[i]);
			}

			int[] parent = new int[N];
			Queue<Line> lines = new PriorityQueue<Line>();
			for (int i = 0; i < N; i++){
				parent[i] = i;

				for (int j = i + 1; j < N; j++){
					lines.add(new Line(i, j, x[i], x[j], y[i], y[j]));
				}
			}

			long sum = 0, cnt = 0;
			while (!lines.isEmpty()){
				Line l = lines.poll();

				if (getParent(parent, l.to) == getParent(parent, l.from)) continue;

				sum += l.len;
				cnt++;
				setParent(parent, l.to, l.from);
				if (cnt == N - 1) break;
			}

			E *= sum;

			System.out.println("#" + tc + " " + String.format("%.0f", E));
		}
	}

	public static int getParent(int[] parent, int k){
		while (k != parent[k]){
			k = parent[k];
		}

		return k;
	}

	public static void setParent(int[] parent, int k, int newParent){
		newParent = getParent(parent, newParent);

		while (true){
			int pk = parent[k];
			parent[k] = newParent;
			if (k == pk) break;
			k = pk;
		}
	}

	static class Line implements Comparable<Line>{
		int from, to;
		long len;

		public Line(int from, int to, long x1, long x2, long y1, long y2){
			this.from = from;
			this.to = to;
			this.len = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
		}

		public int compareTo(Line l){
			if (this.len < l.len) return -1;
			if (this.len > l.len) return 1;

			return 0;
		}
	}
}