[BOJ1774] 우주신과의 교감 (그리디, 크루스칼, MST, 최소신장트리)

 

 

---

문제 링크 

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

1774번: 우주신과의 교감

 

문제 풀이 

크루스칼 알고리즘을 사용하기 위해 노드와 노드 사이의 비용 정보가 필요한데, 2차원 좌표(X, Y)가 주어질 때 노드로 생각하지 못했고, 거리 계산 또한 생각을 하지 못했다. 

해당 문제를 통해 시야가 또 좁아진 점을 반성한다..

 

입력 예시        

4 1 // 노드 수, 연결된 노드 수
1 1 // 노드 1
3 1 // 노드 2
2 3 // 노드 3
4 3 // 노드 4
1 4 // 이미 연결된 노드

 

절차 

1) 인덱스 번호를 노드의 번호로 지정 하여 좌표 값을 저장한다 

2차원 좌표라 생각을 못했는데, 각 입력 라인이 노드를 나타내었

 

Point 클래스 생성 

static class Point {
        int num; // 노드 번호 (=인덱스)
        double x;
        double y;
        //.. 
}

 

2) 2중 for문을 돌며 (중복x) 노드별 좌표간 거리값을 계산한 뒤 정보를 저장한다 

 

Node 클래스 생성 

static class Node implements Comparable<Node> {
        int from;
        int to;
        double cost;
        
        //...
}

 

참고. 2차원 좌표계에서 두 점 사이의 거리 계산 

공식을 사용해서 두 점 사이의 거리를 구하는 방법: 7 단계 (이미지 포함) - wikiHow

 

거리 계산을 잊어버리다니..

 

3) cost 기준으로 List<Node> 데이터 오름차순 정렬 (Comparable 인터페이스 구현)

4) 이미 연결되어 있는 노드 정보 처리해주기 (union, 합집합 처리)

5) 크루스칼 알고리즘 수행하면서, 노드 연결시 cost 합산 

6) 소수점 자리 처리 후 결과 출력

 

제출 코드

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

public class Main {
    
    static int N, M;

    static List<Node> info;

    static int[] parent;

    static class Point {
        int num;
        double x;
        double y;

        public Point(int num, double x, double y) {
            this.num = num;
            this.x = x;
            this.y = y;
        }
    }

    static class Node implements Comparable<Node> {
        int from;
        int to;

        double cost;

        public Node(int from, int to, double cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node other) {
            if(cost < other.cost) return -1;
            else if(cost == other.cost) return 0;
            return 1;
        }
    }

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        parent = new int[N + 1];
        for(int i = 1; i <= N; i++) parent[i] = i;

        // 노드 정보 저장
        Point[] points = new Point[N + 1];
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            double from = Double.parseDouble(st.nextToken());
            double to = Double.parseDouble(st.nextToken());

            points[i] = new Point(i, from, to);
        }

        // 노드별 거리값 계산 후 저장
        info = new ArrayList<>();
        for(int i = 1; i <= N; i++) {
            for(int j = i + 1; j <= N; j++) {
                Point p1 = points[i];
                Point p2 = points[j];

                double distance = calDistance(p1.x, p1.y, p2.x, p2.y);

                info.add(new Node(p1.num, p2.num, distance));
            }
        }

        // 이미 연결된 노드 처리
        for(int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            if(!unionFind(from, to)) {
                union(from, to);
            }
        }
    }

    static double calDistance(double x1, double y1, double x2, double y2) {
        double v1 = Math.pow((x1 - x2), 2);
        double v2 = Math.pow((y1 - y2), 2);
        return Math.sqrt(v1 + v2);
    }

    static int getParent(int node) {
        if(parent[node] == node) return node;

        return parent[node] = getParent(parent[node]);
    }

    static void union(int a, int b) {
        int parentA = getParent(a);
        int parentB = getParent(b);

        if(parentA < parentB) parent[parentB] = parentA;
        else parent[parentA] = parentB;
    }

    static boolean unionFind(int a, int b) {
        int parentA = getParent(a);
        int parentB = getParent(b);

        return parentA == parentB;
    }

    
    static void pro() {
        // cost 오름차순으로 정렬
        Collections.sort(info);

        // 크루스칼 알고리즘 수행
        double result = 0.0;
        for(Node node : info) {
            if(!unionFind(node.from, node.to)) {
                union(node.from, node.to);
                result += node.cost;
            }
        }

        System.out.println(String.format("%.2f", result)); // 결과 출력
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}

 

---

참고

https://steady-coding.tistory.com/120

[BOJ] 백준 1774번 : 우주신과의 교감 (JAVA)