[Algorithm] 백준 MST 문제 - 별자리 만들기(4386) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 별자리 만들기 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/4386

4386번: 별자리 만들기

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;
import static java.lang.Double.parseDouble;
public class Main {
    
    static int n; // n개의 별
    static int[] parent; // 부모 노드
    static int[] count; // 자식 노드 개수
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        parent = new int[n]; // 초기화
        count = new int[n];
        double[][] star = new double[n][2];
        
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            double x = parseDouble(st.nextToken());
            double y = parseDouble(st.nextToken());
            star[i][0] = x;
            star[i][1] = y;
            parent[i] = i; // 초기화는 부모 노드 = 자식 노드
            count[i] = 1; // 자신을 포함해야하므로 개수 1로 초기화
        }
        if (n == 1) {
            System.out.println(0.00); // n == 1이라면 거리 측정 불가 0
            return;
        }
        
        System.out.printf("%.2f", getDistance(star));
    }

    // 우선순위 큐에 거리를 입력한 후 하나씩 빼며 유니온 파인드 진행
    // count[p1]이 n개를 만족한다면 모든 자식 노드가 하나의 루트를 공유하므로 mst 완성
    static double getDistance(double[][] star) {
        Queue<Star> queue = new PriorityQueue<>(Comparator.comparing((Star s) -> s.distance));
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double distance = Math.sqrt(Math.pow((star[i][0] - star[j][0]), 2) + Math.pow((star[i][1] - star[j][1]), 2));
                queue.add(new Star(i, j, distance)); // 우선순위 큐에 별 간의 거리 입력
            }
        }
        
        double distance = 0.0;
        while(!queue.isEmpty()) {
            Star s = queue.poll();
            int p1 = find(s.idx1);
            int p2 = find(s.idx2);

            if (p1 != p2) { // 두 부모가 다른 경우에만 유니온 (사이클 방지)
                union(p1, p2); // 유니온
                distance += s.distance; // 거리 업데이트
            }

            if (count[p1] == n) break; // 만약 개수가 n개가 된다면 탐색 종료
        }
        
        return distance; // 거리 리턴
    } 
    
    
    static int find(int child) { // 경로 압축으로 find
        if (parent[child] == child) return child;
        return parent[child] = find(parent[child]);
    }
    
    static void union(int p1, int p2) { // 유니온
        parent[p2] = p1;
        count[p1] += count[p2]; // p2를 부모로 가지는 자식 노드들의 개수를 count[p1]에 더해주기
        count[p2] = 0;
    }
    
    static class Star {
        int idx1; // 별 첫번째
        int idx2; // 별 두번째
        double distance; // 두 별 간의 거리
        
        Star (int idx1, int idx2, double distance) {
            this.idx1 = idx1;
            this.idx2 = idx2;
            this.distance = distance;
        }
    }
}

 

2. 풀이 중점 사항

 

이번 문제는 MST 문제로, 두 별사이의 거리를 우선순위 큐에 저장한 후, 모든 노드가 하나의 경로로 이어질 수 있도록 유니온 파인드를 적용하는 방법으로 해결할 수 있었습니다.

 

우선순위 큐

 

MST에서 크루스칼 알고리즘을 사용한다면 우선순위 큐를 활용하여 간선의 가중치를 오름차순 형태로 빼낼 수 있습니다.

다른 문제와 달리 이 문제는 간선의 길이를 제공하지 않으므로 두 별자리의 계산 공식 (두 점 사이의 거리)를 활용하여 값을 구하고 이를 우선순위 큐에 넣는 방법을 활용해야 합니다.

 

Queue<Star> queue = new PriorityQueue<>(Comparator.comparing((Star s) -> s.distance));

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        double distance = Math.sqrt(Math.pow((star[i][0] - star[j][0]), 2) + Math.pow((star[i][1] - star[j][1]), 2));
        queue.add(new Star(i, j, distance)); // 우선순위 큐에 별 간의 거리 입력
    }
}

 

람다를 활용하여 distance로 정렬할 수 있도록 한 후, 두 점사이의 거리 공식을 활용하고 큐에 넣습니다.

 

 

유니온 파인드

 

static int find(int child) { // 경로 압축으로 find
    if (parent[child] == child) return child;
    return parent[child] = find(parent[child]);
}

static void union(int p1, int p2) { // 유니온
    parent[p2] = p1;
    count[p1] += count[p2]; // p2를 부모로 가지는 자식 노드들의 개수를 count[p1]에 더해주기
    count[p2] = 0;
}

 

find(), union()은 정형화된 메서드입니다. 경로압축으로 자식 노드가 가리키는 부모 노드를 찾으면서 업데이트합니다.

union()은 찾은 두 부모를 하나로 연결하는 과정으로, parent[p2]의 값을 p1으로 업데이트하여, p2의 부모가 p1이 되도록 합니다.

 

하단에 count[]코드는 n개의 별자리를 만족시키면 종료해야 합니다. 이 경우, 부모 노드가 가지고 있는 자식 노드들의 개수를 합치는 (더 커지는) 부모 노드에 업데이트해주어야 합니다. 

 

따라서, p1에 p2의 자식 노드들의 개수를 더해주고, p2는 더 이상 루트 노드가 아니므로 0으로 업데이트합니다.

 

double distance = 0.0;
while(!queue.isEmpty()) {
    Star s = queue.poll();
    int p1 = find(s.idx1);
    int p2 = find(s.idx2);

    if (p1 != p2) { // 두 부모가 다른 경우에만 유니온 (사이클 방지)
        union(p1, p2); // 유니온
        distance += s.distance; // 거리 업데이트
    }

    if (count[p1] == n) break; // 만약 개수가 n개가 된다면 탐색 종료
}

return distance; // 거리 리턴

 

만약 이미 부모가 같은 경우는, distance를 증가시키면 안 됩니다 (사이클)

이미 같은 부모를 공유한다는 의미는 두 별자리에 대한 distance를 더했음을 의미합니다.

따라서, 이 경우는 패스하고 두 부모가 다른 경우에만 적용할 수 있도록 하였습니다.

 

이상으로 백준 별자리 만들기 풀이를 마치도록 하겠습니다.

감사합니다!!!