[백준][Java] 5081 - Constellations

목차

문제 정보

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

5081번: Constellations

난이도 : Gold 5

유형 : Union-find, 브루트포스

---

문제 풀이

[핵심]

1. 별마다 번호부여하기

2. 별마다 가장 가까운 별들을 구하여 간선 연결해 주기

 

이 문제는 별의 개수와 (x, y) 좌표가 입력으로 주어진다.

union-find를 하기 위해 입력순으로 별마다 번호를 부여하고 x, y값은 클래스를 이용하여 처리하였다.

 

별마다 가까운 별을 구할 때 최적화를 하기 위해 리스트를 이용하여

 

1. (기준 별과 이전까지 비교했던 별들과의 가장 짧은 거리) > (기준 별과 지금 비교하고 있는 별과의 거리)

리스트를 초기화 -> 현재 비교하고 있는 별의 번호를 추가

 

2. (기준 별과 이전까지 비교했던 별들과의 가장 짧은 거리) = (기준 별과 지금 비교하고 있는 별과의 거리)

기존 리스트에 현재 비교하고 있는 별의 번호도 추가

 

이런 로직을 통해서 별마다 가장 가까운 별들을 탐색하여 리스트에 넣은 뒤

기준 별과 리스트에 들어 있는 별들을 연결해 주면 된다.

 

연결은 union-find 기법을 이용

 

필자는 변형된 rank by union 기법을 이용하였다. 

 

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private int n;
    private int tc;
    private Node[] nodes;
    private ArrayList<Integer> minDistanceEdge;
    private int res;

    private class Node {
        int number;
        int x;
        int y;
        int rank;

        public Node(int number, int x, int y) {
            this.number = number;
            this.x = x;
            this.y = y;
            this.rank = -1;
        }
    }

    public int getDistance(Node a, Node b) {
        return Math.abs(a.x - b.x) * Math.abs(a.x - b.x) + Math.abs(a.y - b.y) * Math.abs(a.y - b.y);
    }

    public int find(int x) {
        if (nodes[x].rank < 0) {
            return x;
        }

        return nodes[x].rank = find(nodes[x].rank);
    }

    public void union(int x, int y) {
        int a = find(x);
        int b = find(y);

        if (a == b) {
            return;
        }

        if (nodes[a].rank <= nodes[b].rank) {
            nodes[a].rank += nodes[b].rank;
            nodes[b].rank = a;
        } else {
            nodes[b].rank += nodes[a].rank;
            nodes[a].rank = b;
        }
    }

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        tc = 1;
        while ((n = Integer.parseInt(br.readLine())) != 0) {
            nodes = new Node[n + 1];

            for (int i = 1; i <= n; i++) {
                st = new StringTokenizer(br.readLine());
                nodes[i] = new Node(i, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            }

            for (int i = 1; i <= n; i++) {
                minDistanceEdge = new ArrayList<>();
                
                int minDistance = Integer.MAX_VALUE;

                // Get closest Nodes
                for (int j = 1; j <= n; j++) {
                    if (i == j) continue;

                    int distance = getDistance(nodes[i], nodes[j]);

                    if (minDistance == distance) {
                        minDistanceEdge.add(j);
                    } else if (minDistance > distance) {
                        minDistance = distance;
                        minDistanceEdge.clear();
                        minDistanceEdge.add(j);
                    }

                }

                for (int node : minDistanceEdge) {
                    union(i, node);
                }

                res = 0;
                for (int k = 1; k <= n; k++) {
                    if (nodes[k].rank < 0) {
                        res++;
                    }
                }
            }
            sb.append("Sky " + tc++ + " contains " + res + " constellations.\n");
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}