[백준]1774번 우주신과의 교감 - 자바, Java, 크루스칼 알고리즘

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

1774번: 우주신과의 교감

 
 
아직 연결되지 않은 간선을 찾아서 그중 가장 가까운 것을 찾아서 연결하면 해결이 된다 생각하였고
아래와 같은 코드를 작성했다. 

import java.util.Scanner;

public class B1774 {
	static class Node{
		int x, y;

		public Node(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}


	}

	static boolean[] flag;
	static Node[] nodes;
	static int size1;
	static int result = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		size1 = sc.nextInt(); // 받아야하는 값들
		int size2 = sc.nextInt(); // 이미 연결된 통로들

		nodes = new Node[size1];
		flag = new boolean[size1];
		for (int i = 0; i < size1; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();

			nodes[i] = new Node(a, b);
		}// 입력완료.
		
		for(int i = 0; i < size2; i++) {
			int a = sc.nextInt();			
			int b = sc.nextInt();			
			flag[a-1] = true;
			flag[b-1] = true;
		}// 이 곳이랑 가장 가까운 곳을 찾을 필요가 없다.
		
				
		for(int i = 0; i<size1; i++) { // 이만큼만 동작하면됨
			if(flag[i] == false) { // 아직 못찾은 친구면
				flag[i] = true;
				
				dijkstra(i,nodes[i].x , nodes[i].y); // 함수 실행.
			}
		}
		System.out.print(Math.round(result*2)+".00");
		
		

	}//main 종료
	
	public static void dijkstra(int index,int x, int y) {
		
		int num = x+y; // 이녀석과의 최솟값을 찾아야함
		// index는 빼고
		
		int min = Integer.MAX_VALUE;
		int idx = -1;
		for(int i = 0; i < size1; i++) {
			if(i == index) {
				continue;
			}
			int a = nodes[i].x;
			int b = nodes[i].y;
			int c = a + b;
			if(min> Math.abs(num-c)) {
				min = Math.abs(num-c);
				idx = i;
			}
		}// 차이의 최솟값을 찾았어? 그럼 계산하셔야지
		
		result += min;
		
	}//dijkstra 함수 끝
	
	
	
}

하지만 이는 잘못된 방법이었다. 물론 운이 좋다면 가장 근처에 있는 간선들을 연결해 최소경로를 구성할 수 있겠지만, 연결되지 않은 경로들끼리 연결했을 때 그 값이 더 작을 수도 있기 떄문이다.
뿐만아니라 연결된 간선도 방문처리를 해줄 경우 모든 간선이 연결되어있는 상태가 아닐 수 있어 빵상을 모든 곳에 전파할 수 없더다.
 
이러한 방식에서는 최소 스패닝 트리 ( MST ) 알고리즘을 사용해야한다.
 

MST 방식 2가지

MST의 구현 방법
1. Kruskal MST 알고리즘
탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

MST(최소 비용 신장 트리) 가 1) 최소 비용의 간선으로 구성됨 2) 사이클을 포함하지 않음 의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 한다.
간선 선택을 기반으로 하는 알고리즘이다.
이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법이다.

그래프의 간선들을 가중치의 오름차순으로 정렬한다.
정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
즉, 가장 낮은 가중치를 먼저 선택한다.
사이클을 형성하는 간선을 제외한다.
해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다.
참고 구체적인 내용은 Kruskal MST 알고리즘이란 참고

2. Prim MST 알고리즘
시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장 해나가는 방법

정점 선택을 기반으로 하는 알고리즘이다.
이전 단계에서 만들어진 신장 트리를 확장하는 방법이다.

시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함된다.
앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.
즉, 가장 낮은 가중치를 먼저 선택한다.
위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복한다.
참고 구체적인 내용은 Prim MST 알고리즘이란 참고
출처 : https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

 
이 문제는 싸이클을 포함하지 않으며 최소 신장 트리를 구하는 문제이기때문애 '크루스칼 알고리즘' 을 사용해 풀어야한다.

의문 우선순위큐에 거리에 따른 값을 담는다하면 예외가 발생하지 않을까?

부모가 같지않은 간선들중 가장 거리가 짧은 것을 연산하기에 괜찮다.
-> 조건문의 실행은 부모간선의 동일 여부 확인이다.
 
그런데도 많은 고난이 있었다..

 
이 문제에서 틀릴 수 있는 모든 경우의 수는 다 틀렸다고 볼 수 있다.
덕분에 크루스칼 알고리즘에 대한 깊은 탐구가 있을 수 있었다.
 
크루스칼 알고리즘 준비물
1. 부모를 담을 배열 int p[]
2. 간선간의 정보와 간선거리
3. 크루스칼 함수, union 함수, 부모찾기 함수
 
 
 

코드

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static int connected;

    static class Node implements Comparable<Node> {
        int N, V;
        double w;

        public Node(int x, int y, double w) {
            super();
            this.N = x;
            this.V = y;
            this.w = w;
        }

        @Override
        public int compareTo(Node o) {
            // TODO Auto-generated method stub
            return Double.compare(this.w, o.w);
            // 앞의 값이 더 작으면 -1 크면 1 같으면 0 반환
        }

    }

    static class Temp {
        int x, y;

        public Temp(int x, int y) {
            super();
            this.x = x;
            this.y = y;

        }

    }

    static int size1;
    static Temp[] temps;
    static PriorityQueue<Node> nodes;
    static int[] p;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        size1 = sc.nextInt(); // 받아야하는 값들
        int size2 = sc.nextInt(); // 이미 연결된 통로 갯수

        temps = new Temp[size1];
        nodes = new PriorityQueue<>();
        p = new int[size1];

        for (int i = 0; i < size1; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            temps[i] = new Temp(a, b);
            p[i] = i; // 초기값 ; 자기 자신이 부모
        } // 각 간선의 정보를 저장합니다.

        for (int i = 0; i < size1; i++) {
            for (int j = i + 1; j < size1; j++) {
                double distance = Math
                        .sqrt(Math.pow(temps[i].x - temps[j].x, 2) + Math.pow(temps[i].y - temps[j].y, 2));
                nodes.add(new Node(i, j, distance));
            }
        } // 각 정점에서 뻗어나가는 가장 가까운 경로들을 거리순으로 저장함

        for (int i = 0; i < size2; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            union(a, b);
        }

        System.out.printf("%.2f", kruscal(connected));

    }// main 종료

    public static void union(int a, int b) {
        a = findparent(a);
        b = findparent(b);
        if (a == b)
            return;
        ++connected;
        if (a > b) {
            p[a] = b;
        } else {
            p[b] = a;
        }
    }

    public static int findparent(int num) {
        if (p[num] == num) {
            return p[num];
        } else {
            return p[num] = findparent(p[num]);
        }
    }

    public static double kruscal(int cnt) {
        int Cnt = cnt + 1;
        double result = 0.0;
        while (!nodes.isEmpty()) {
            Node node = nodes.poll();
            if (findparent(node.N) != findparent(node.V)) { // 부모가 다르면 함수 실행

                result += node.w;
                Cnt++;
                if (Cnt == size1) {
                    return result;
                }
                union(node.N, node.V);

            }
        }

        return result;
    }

}

 
유의할점이 있다.
union연산을 할때
같은 부모를 참조하면서 연산 횟수를 차지하고 있다면 kruscal 함수의 Cnt++ 연산에 방해를 주기에
union 함수안에 connect++을 넣어 진짜 union연산이 된 횟수를 저장해 오류가 없이 만들어야한다.