[백준] 1774: 우주신과의 교감 - 최소신장트리(Minimum Spanning Tree, MST) + 크루스칼(Kruskal) JAVA

https://www.acmicpc.net/problem/1774

1774번: 우주신과의 교감

 

단순 크루스칼 문제입니다.

다만, 여기서 신경써야하는점은 황선자 씨와 이미 연결된, 혹은 우주신들과 연결된 통로들이 마지막 줄에 M개의 줄로 주어집니다.

이떄,

1. unionParent로 parent를 합쳐버림으로써 edges에 애초에 들어가지 못하게 하여 하나의 그래프로 만들어버리는 경우가 있고

2. edges에 cost가 0 인 상태로 넣어서 계산을 하더라도 cost는 0으로 더해지기에 별 상관없이 진행하는 방안이 있습니다.

 

문제답을 내는데 필요한것들은

1. Math.pow((a - b), 2) 를 통해 점과 점 사이의 거리를 구하는 공식

2.      System.out.println(String.format("%.2f", result)); 를 통하여 소수점 2자리 반올림하는 공식

이 있습니다.

 

import java.util.*;



public class Main {
	public static int N,M;
	public static int[] parent = new int[1001];
	public static ArrayList<Edge> edges = new ArrayList<>();
	public static ArrayList<Node> nodes = new ArrayList<>();
	public static double result = 0;
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	N = sc.nextInt(); M = sc.nextInt();
    	
    	//싸이클 판별을 위한 부모배열을 초기화합니다.
    	for(int i=1;i<=N;i++) {
    		parent[i] = i;
    	}
    	
    	//노드의 x좌표, y좌표를 저장합니다.
    	for(int i=0;i<N;i++) {
    		double x = Double.parseDouble(sc.next());
    		double y = Double.parseDouble(sc.next());
    		nodes.add(new Node(x, y));
    	}
    	
    	//이미 연결된 노드들의 distance 는 0 입니다. TODO : 이게 아니면, unionFind로 연결해서 진행합니다.
    	for(int i=0;i<M;i++) {
    		int start = sc.nextInt();
    		int end = sc.nextInt();
//    		edges.add(new Edge(start, end, 0));
    		unionParent(start, end);
    	}
    	
    	//모든 우주신들간의 간선 정보와 간선 길이(cost)를 간선리스트(edges)에 젖아합니다.
    	for(int i=0; i<N;i++) {
    		for(int j=i+1;j<N;j++) {
    			Node startNode = nodes.get(i);
    			Node endNode = nodes.get(j);

    			double cost = Math.sqrt(Math.pow(startNode.x - endNode.x, 2) + Math.pow(startNode.y - endNode.y,  2));
    			edges.add(new Edge(i+1, j+1, cost));
    		}
    	}
    	Collections.sort(edges);
    	
    	for(int i=0;i<edges.size();i++) {
    		int a = edges.get(i).nodeA;
    		int b = edges.get(i).nodeB;
    		double cost = edges.get(i).distance;
    		
    		if( findParent(a) != findParent(b) ) {
    			unionParent(a, b);
    			result += cost; 
    		}
    	}
    	
    	System.out.println(String.format("%.2f", result));
    	
    	
    }
    
    public static int findParent(int x) {
    	if( x == parent[x] ) return x;
    	return parent[x] = findParent(parent[x]);
    }
    
    public static void unionParent(int a, int b) {
    	a = findParent(a);
    	b = findParent(b);
    	
    	if( a < b ) parent[b] = a;
    	else parent[a] = b;
    }
    
}

class Node {
	double x;
	double y;
	public Node(double x, double y) {
		this.x = x;
		this.y = y;
	}
}

class Edge implements Comparable<Edge>{
	int nodeA;
	int nodeB;
	double distance;
	
	public Edge(int nodeA, int nodeB, double distance) {
		this.nodeA = nodeA;
		this.nodeB = nodeB;
		this.distance = distance;
	}
	
	@Override
	public int compareTo(Edge other) {
		if(this.distance < other.distance) {
			return -1;
		}else if(this.distance > other.distance) {
			return 1;
		}
		return 0;
	}
	
}