[백준 4386/JAVA] 별자리 만들기

문제

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

풀이

• 문제에서 좌표가 노드로 주어졌다. 노드 마다 해당되는 좌표를 저장해야 하므로 Coordinate 클래스를 만들어 x좌표, y좌표를 저장했다. 그리고 부모 노드가 무엇인지 찾기 쉽도록 좌표마다 노드 번호를 부여했다.
• 좌표 간 거리(노드 간의 거리)가 주어지지 않았으므로 직접 계산해서 따로 저장해야 한다. Edge 클래스를 만들어 노드1, 노드2, 노드 1과 2 사이의 거리를 저장했다.
• Kruskal 알고리즘을 사용하여 MST를 구했다. : Edge에 저장된 거리가 가까운 순으로 정렬 후 앞에서부터 하나씩 edge를 꺼내 MST 완성

1. 좌표 마다 노드 번호 매기기
   (1,0)(1,0) = 노드 1
   (2,0)(2,0) = 노드 2
   ...
   입력 받는 순서대로 좌표를 Coordinate클래스에 넣고 노드 번호를 부여했다.
   Coordinate객체를 coordinateList에 차례로 저장했다.

2. 노드 간의 거리 구하기
   coordinateList에서 노드를 차례로 꺼내 두 노드 사이의 거리에 해당하는 모든 경우의 수를 구하고, Edge클래스에 저장했다.
3. Kruskal로 MST 구하기

코드

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

public class Main {
    static int[] parent;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        double sum = 0;

        int N = Integer.parseInt(br.readLine());
        List<Coordinate> coordinateList = new ArrayList<>();
        List<Edge> edgeList = new ArrayList<>();
        parent = new int[N+1];

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

        //좌표를 list에 저장
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            double x = Double.parseDouble(st.nextToken());
            double y = Double.parseDouble(st.nextToken());

            Coordinate c = new Coordinate(x, y, i);
            coordinateList.add(c);
        }

        //coordinatelist에 저장된 좌표끼리 비교하여 각각의 거리 구하기
        for(int i=0; i<coordinateList.size(); i++){
            for(int j=i+1; j<coordinateList.size(); j++){
                Coordinate current = coordinateList.get(i);
                Coordinate next = coordinateList.get(j);

                double dist = Math.sqrt((current.x - next.x)*(current.x - next.x)+
                        (current.y - next.y)*(current.y - next.y));

                edgeList.add(new Edge(current.cid, next.cid, dist));
            }
        }

        //MST구하기
        Collections.sort(edgeList);

        for(int i=0; i<edgeList.size(); i++){
            Edge edge = edgeList.get(i);
            if(!isSameParent(edge.a, edge.b)){
                union(edge.a, edge.b);
                sum += edge.dist;
            }
        }
        System.out.printf("%.2f", sum);
    }
    static boolean isSameParent(int a, int b){
        a = find(a);
        b = find(b);
        if(a != b)
            return false;
        return true;
    }
    static int find(int a){
        if(parent[a] == a)
            return a;
        return parent[a] = find(parent[a]);
    }

    static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a < b) parent[b] = a;
        else if(a > b) parent[a] = b;
    }

}
class Coordinate {
    //cid : 좌표의 노드번호
    //x, y : 좌표
    int cid;
    double x, y;
    Coordinate(double x, double y, int cid){
        this.cid = cid;
        this.x = x;
        this.y = y;
    }
}
class Edge implements Comparable<Edge>{
    //a, b : cid1, cid2
    //dist : cid1, cid2 사이의 거리
    int a, b;
    double dist;

    Edge(int a, int b, double dist){
        this.a = a;
        this.b = b;
        this.dist = dist;
    }
    public int compareTo(Edge e){
        if(this.dist > e.dist) return 1;
        else if(this.dist == e.dist) return 0;
        else return -1;
    }
}

 

Note

• 노드 간 거리를 구하는 이중 for문에서 i, j의 시작, 끝 범위를 잘못 설정하여 오답. for문 조건 실수는 언제 안 할까
• int, double 주의
• parent[N+1]에는 인덱스와 초기화할 숫자가 같아야 해서 1~N이 저장되지만, list에는 인덱스 0부터 객체를 담아야 꺼낼 때도 조건문을 쓸 때 안 헷갈린다. 둘을 같은 for문에서 초기화하지 말자.