1251. [S/W 문제해결 응용] 4일차 - 하나로

당신은 인도네시아 내의 N개의 섬들을 연결하는 교통시스템 설계 프로젝트인 ‘하나로’를 진행하게 되었습니다.

하나로 프로젝트는 천혜의 자연을 가진 인도네시아의 각 섬 간 교통이 원활하지 않아 관광 산업의 발전을 저해하는 요소를 줄이고 부가 가치를 창출하고자 진행하는 프로젝트입니다.

본 프로젝트에서는 인도네시아 내의 모든 섬을 해저터널로 연결하는 것을 목표로 합니다.

해저터널은 반드시 두 섬을 선분으로 연결하며, 두 해저 터널이 교차된다 하더라도 물리적으로는 연결되지 않는 것으로 가정합니다.

아래 그림 1과 같은 경우, A섬에서 D섬으로는 연결되었지만 A섬으로부터 B섬, C섬에는 도달 할 수 없기 때문에 연결되지 않은 것입니다.

다음 두 가지의 경우는 모든 섬이 연결된 것입니다.

위와 같은 방법을 통해 인도네시아 내의 모든 섬들을 연결해야 하는 프로젝트입니다.

그림 3에서 B와 A처럼 직접적으로 연결된 경우도 있지만, B와 C처럼 여러 섬에 걸쳐 간접적으로 연결된 경우도 있습니다.

다만 인도네시아에서는 해저터널 건설로 인해 파괴되는 자연을 위해 다음과 같은 환경 부담금 정책이 있습니다.

• 환경 부담 세율(E)과 각 해저터널 길이(L)의 제곱의 곱(E * L^2)만큼 지불

총 환경 부담금을 최소로 지불하며, N개의 모든 섬을 연결할 수 있는 교통 시스템을 설계하시오.

64비트 integer 및 double로 처리하지 않을 경우, overflow가 발생할 수 있습니다 (C/C++ 에서 64비트 integer는 long long 으로 선언).

위의 그림 2은 환경 부담금을 최소로 하며 모든 섬을 연결하고 있지만, 그림 3는 그렇지 않음을 알 수 있습니다.

[입력]

가장 첫 줄은 전체 테스트 케이스의 수이다.

각 테스트 케이스의 첫 줄에는 섬의 개수 N이 주어지고 (1≤N≤1,000),

두 번째 줄에는 각 섬들의 정수인 X좌표, 세 번째 줄에는 각 섬들의 정수인 Y좌표가 주어진다 (0≤X≤1,000,000, 0≤Y≤1,000,000).

마지막으로, 해저터널 건설의 환경 부담 세율 실수 E가 주어진다 (0≤E≤1).

[출력]

각 테스트 케이스의 답을 순서대로 출력하며, 각 케이스마다 줄의 시작에 “#C”를 출력하여야 한다. 이때 C는 케이스의 번호이다.

같은 줄에 빈칸을 하나 두고, 주어진 입력에서 모든 섬들을 잇는 최소 환경 부담금을 소수 첫째 자리에서 반올림하여 정수 형태로 출력하라.

입력

10
2
0 0
0 100
1.0
4
0 0 400 400
0 100 0 100
1.0
6
0 0 400 400 1000 2000
0 100 0 100 600 2000
0.3
9
567 5 45674 24 797 29 0 0 0
345352 5464 145346 54764 5875 0 3453 4545 123
0.0005

출력

#1 10000
#2 180000
#3 1125000
. . .

풀이

이 문제를 풀때는, x,y 좌표의 역할과 정점의 번호가 서로 다른 목적을 갖고 있다는 걸 생각해야 한다. x,y 좌표는 단순히 정점들간의 거리 계산을 위한 것이기에, 정점의 번호는 우리가 직접 지정해주면 된다.

문제에서 x, y 좌표를 차례대로 제시하였으므로, 이를 참고하여 간선정보를 담는 Edge 객체를 생성할 때 정점들 번호를 1부터 매겨나가고, 각 정점(섬)들간의 거리를 함께 담아주면 된다.

크루스칼 알고리즘을 적용하기 위해 거리가 짧은 것을 기준으로 정렬하는 과정도 필요하다.

자바 풀이

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

class Edge implements Comparable<Edge> {
    int a; // 섬 번호
    int b; // 다른 섬 번호
    double dist; // 거리

    public Edge(int a, int b, double dist) {
        this.a = a;
        this.b = b;
        this.dist = dist;
    }

    @Override
    public int compareTo(Edge e) {
        return Double.compare(this.dist, e.dist);
    }
}

public class Main {

    static int[] parent; // 정점별 연결 트리의 루트 노드
    static int[] xlist; // 정점별 x좌표 저장 배열
    static int[] ylist; // 정점별 y좌표 저장 배열
    static double sum = 0; // 환경부담금 총합
    static ArrayList<Edge> elist; // 정점들간의 거리를 기록한 Edge 배열

    static int findP(int x) {
        if (parent[x] != x){
        	return parent[x] = findP(parent[x]);
        }
        return parent[x];
    }

    static void union(int n1, int n2) {
        int p1 = findP(n1);
        int p2 = findP(n2);

        // p1에 p2를 합침
        parent[p1] = p2;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        for (int tc = 1; tc <= T; tc++) {
            // 섬들의 개수
            int N = Integer.parseInt(br.readLine().trim());
            // 최소 환경 부담금 초기화
            sum = 0;
            // 정점 간 비중을 포함하는 Edge 배열
            elist = new ArrayList<>();
            // parent 및 정점들 x,y 좌표 기록 배열 초기화
            parent = new int[N + 1];
            xlist = new int[N + 1];
            ylist = new int[N + 1];
            for (int i = 1; i <= N; i++) parent[i] = i; // parent 배열 초기화
            // 정점(섬)들의 개수만큼 x좌표 저장함
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                xlist[i] = Integer.parseInt(st.nextToken());
            }
            // 정점(섬)들의 개수만큼 y좌표 저장함
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                ylist[i] = Integer.parseInt(st.nextToken());
            }
            // 환경 부담 세율 E
            double E = Double.parseDouble(br.readLine().trim());
            // 좌표들 돌면서 내부 값 사용해서 거리를 포함한 Edge 제작
            for (int i = 1; i < N; i++) {
                for (int j = i+1; j <= N; j++) {
                    // 거리 구하기 - 루트 아래 X좌표 빼기 곱 + Y좌표 빼기 곱
                    double dist = Math.sqrt(Math.pow(xlist[i] - xlist[j], 2) + Math.pow(ylist[i] - ylist[j], 2));
                    // 각 좌표간 거리 가지는 Edge 객체 생성 후 배열에 저장
                    elist.add(new Edge(i, j, dist));
                }
            }
            // dist 기준으로 정렬
            Collections.sort(elist);
            // elist에서 작은 것부터 골라서 union, 이때 사이클 생기는지 여부 확인해야 함
            for (int i = 0; i < elist.size(); i++) {
                Edge e = elist.get(i);
                // 두 섬을 추출
                int fi = e.a;
                int si = e.b;
                // 두 섬의 그룹이 같으면 사이클 생기므로 PASS
                if(findP(fi) == findP(si)) continue;
                // 그게 아니라면 union
                union(fi,si);
                // 최소 환경 부담금에 더함 (환경 부담 세율과 각 해저터닐 길이의 제곱의 곱)
                sum += Math.pow(e.dist, 2) * E;
            }
            // 최소 환경부담금 출력
            System.out.print("#" + tc + " " + Math.round(sum));
            System.out.println();
        }
    }
}