[SWEA/Java] 1251. 하나로

[SWEA/Java] 1251. 하나로

SW Expert Academy

---

문제 해석

이 문제는 인도네시아의 N개 섬을 연결하는 교통 시스템을 설계하는 것이다. 각 섬은 좌표로 주어지며, 섬들을 연결하는 해저터널의 비용은 터널 길이의 제곱과 환경 부담 세율의 곱으로 계산된다. 주어진 조건 하에서 모든 섬이 연결될 수 있도록 하면서 환경 부담금을 최소화하는 해결책을 찾아야 한다. 문제의 요구 사항은 그래프의 최소 신장 트리를 구하는 것과 유사하다고 볼 수 있다.

풀이 과정

섬들 간의 모든 가능한 연결을 고려하여 각 연결 비용을 계산한 후, 이를 기반으로 최소 신장 트리(MST)를 구성해야 한다. 각 연결 비용은 주어진 섬들의 좌표를 이용하여 유클리드 거리의 제곱으로 계산되며, 이 값에 환경 부담 세율 E를 곱한다. 이 문제를 해결하기 위해 프림 알고리즘 또는 크루스칼 알고리즘을 사용할 수 있다. 계산된 최소 신장 트리의 총 비용을 반올림하여 출력해야 한다.

코드

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

public class Main {
    // Edge 클래스는 각 섬 간의 연결을 나타내며, 비교가 가능하도록 Comparable 인터페이스를 구현한다.
    static class Edge implements Comparable<Edge> {
        int start, end;  // 시작 섬과 끝 섬의 인덱스
        double cost;     // 연결 비용

        Edge(int start, int end, double cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }

        // 비용을 기준으로 오름차순 정렬하기 위한 메소드
        @Override
        public int compareTo(Edge o) {
            return Double.compare(this.cost, o.cost);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스의 수를 입력받음
        for (int tc = 1; tc <= T; tc++) {  // 각 테스트 케이스에 대해 반복
            int N = Integer.parseInt(br.readLine());  // 섬의 개수
            int[] x = new int[N];  // 섬들의 X 좌표
            int[] y = new int[N];  // 섬들의 Y 좌표
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                x[i] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                y[i] = Integer.parseInt(st.nextToken());
            }
            double E = Double.parseDouble(br.readLine()); // 환경 부담 세율

            // 모든 가능한 연결을 우선순위 큐에 추가
            PriorityQueue<Edge> pq = new PriorityQueue<>();
            for (int i = 0; i < N; i++) {
                for (int j = i + 1; j < N; j++) {
                    double dist = Math.pow(x[i] - x[j], 2) + Math.pow(y[i] - y[j], 2);
                    pq.add(new Edge(i, j, E * dist));  // 비용 계산 후 큐에 추가
                }
            }

            // 크루스칼 알고리즘으로 최소 신장 트리 구성
            int[] parent = new int[N];  // 각 섬의 부모를 저장하는 배열
            for (int i = 0; i < N; i++) {
                parent[i] = i;  // 초기화
            }
            double result = 0;
            int count = 0;
            while (!pq.isEmpty()) {
                Edge edge = pq.poll();  // 가장 비용이 낮은 연결을 꺼냄
                if (union(edge.start, edge.end, parent)) {  // 사이클이 없으면 해당 간선을 추가
                    result += edge.cost;
                    if (++count == N - 1) break;  // 모든 섬이 연결되면 종료
                }
            }

            // 결과 출력
            bw.write("#" + tc + " " + Math.round(result) + "\n");
        }
        bw.flush();
        bw.close();
    }

    // 유니온 파인드의 'find' 함수
    static int find(int a, int[] parent) {
        if (a == parent[a]) return a;
        return parent[a] = find(parent[a], parent);
    }

    // 유니온 파인드의 'union' 함수
    static boolean union(int a, int b, int[] parent) {
        int rootA = find(a, parent);
        int rootB = find(b, parent);
        if (rootA != rootB) {
            parent[rootB] = rootA;  // 두 섬을 연결
            return true;
        }
        return false;
    }
}

시간 복잡도 분석

시간 복잡도는 크루스칼 알고리즘을 사용했기 때문에 𝑂(𝐸log⁡𝐸)이다. 여기서 𝐸E는 섬 간의 가능한 모든 연결 수이며, 섬의 개수 𝑁에 따라 𝑂(𝑁^2)의 연결이 가능하다.

느낀점

이 문제를 통해 최소 신장 트리 알고리즘의 중요성을 다시 한 번 확인할 수 있었다. 또한, 실수 연산과 관련된 문제에서는 자료형 선택에 주의해야 함을 알게 되었다.