[백준] 1774번 우주신과의 교감 (java, mst, 크루스칼)

www.acmicpc.net/problem/1774

1774번: 우주신과의 교감

m개의 통로가 연결되어있다고 해서 이미 연결된 간선의 수 (cnt) = m으로 초기화했다가 틀렸다.

 

 

주어진 연결된 통로가 중복되거나 사이클을 형성하지 않도록 m개의 통로도 union-find 함수를 이용해서 연결해주어야한다. 

 

그 다음에는 순차대로 거리가 작은 순으로 그래프에 추가해준다.

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Edge { // 각 우주신들의 좌표
	int x,y;
	public Edge(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
	
}

class God implements Comparable<God>{ // 연결된 노드 x,y와 거리에 대한 정보
	int x;
	int y;
	double dist;
	
	public God(int x, int y, double dist) {
		super();
		this.x = x;
		this.y = y;
		this.dist = dist;
	}
	@Override
	public int compareTo(God o) {
		if(this.dist>o.dist)return 1;
		else if(this.dist<o.dist)return -1;
		else return 0;
	}	
	
}


public class Main {
	static int n,m;
	static ArrayList<God>diff;
	static Edge[] list;
	static double answer;
	static int[] parent;
	static int cnt;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		parent=new int[n+1];
		for (int i = 0; i < n+1; i++) {//속한 집합 초기화 
			parent[i]=i;
		}
		list=new Edge[n+1];
		diff=new ArrayList<>();
		for (int i = 1; i <n+1; i++) {// 각 우주신들 좌표 정보 담음
			int x=sc.nextInt();
			int y=sc.nextInt();
			list[i]=new Edge(x,y);
		}
		for (int i = 1; i < n+1; i++) {
			for (int j = i+1; j < n+1; j++) { // 각 노드 간 거리의 차이구함
				double diffx=Math.abs(list[i].x-list[j].x);
				double diffy=Math.abs(list[i].y-list[j].y);
				diff.add(new God(i,j,diffx*diffx+diffy*diffy));
			}
		}
		for (int i = 0; i < m; i++) { //연결된 통로를 사이클없이 연결해준다. 비용은 0
			int a=sc.nextInt();
			int b=sc.nextInt();
			a=find(a);
			b=find(b);
			//여기서 주의
			//중복연결된 값이 들어올 수 있다. 모든 연결된 간선이 추가될 수는 없고 이미 연결되지 않은 경우에만 cnt+1을 해준다.
			if(a!=b) {
				cnt+=1;
				if(a>b) {
					parent[a]=b;
				}else {
					parent[b]=a;
				}
			}
		}

		Collections.sort(diff); //거리 오름차순 정렬 

		for(God e:diff) {
			union(e.x,e.y,e.dist); // 나머지 통로들 연결해준다
			if(cnt==n)break;//연결 끝
		}
		System.out.printf("%.2f\n",answer);
		
		
	}
	private static void union(int x, int y, double dist) {
		x=find(x);
		y=find(y);
		if(x!=y) {
			answer+=Math.sqrt(dist);
			cnt+=1;
			if(x<y) {
				parent[y]=x;
			}else {
				parent[x]=y;
			}
		}
		
	}
	private static int find(int x) {
		if(x==parent[x])return x;
		return x=find(parent[x]);
	}
}