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

하나로

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//크루스칼 방법으로 풀고, 모든 간선의 크기를 계산해서 오름차순으로 정렬한다.결국에는 조합-> 비트마스킹을 이용한 조합
public class Solution{
    static List<Edge> list;
    static int N;
    static int[] subset;
    static double E;
    static int[] Parent;
    static class Edge implements Comparable<Edge>{
        int from, to;
        double weight;
        public Edge(int start, int end, double weight) {
            this.from = start;
            this.to = end;
            this.weight = weight;
        }
        @Override
        public int compareTo(Edge o) {
            double result=(this.weight-o.weight);
            if(result<0) return-1;
            else return 1;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int T=Integer.parseInt(st.nextToken());
        //테스트케이스
        for (int tc = 1; tc <=T ; tc++) {
            st=new StringTokenizer(br.readLine());
            N=Integer.parseInt(st.nextToken());
            //각각 정점의 번호를 x의 index와 같다고 한다.
            long[][] map=new long[N][2];

            //간선을 저장할 Edge리스트를 생성한다.
            list=new LinkedList<>();
            subset=new int[2];
           Parent=new int[N];
            //x좌표 입력받기
            st=new StringTokenizer(br.readLine());
            for (int i = 0; i < N ; i++) {
                map[i][0]=Long.parseLong(st.nextToken());
            }
            //y좌표 입력받기
            st=new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                map[i][1]=Long.parseLong(st.nextToken());
            }
            st=new StringTokenizer(br.readLine());
            E=Double.parseDouble(st.nextToken());
            //간선리스트 완성
            combi(map,0,0);
            //간선리스트 정렬
            Collections.sort(list);
            makeSubset();
            double result=0;
            int cnt=0;
            for (Edge e:list) {
                if(union(e.from,e.to)){
                    ++cnt;
                    result+= e.weight;
                }
                if(cnt==N-1)
                    break;;
            }
            System.out.printf("#%d %d%n",tc,Math.round(result));
        }
    }

    private static boolean union(int from, int to) {
        int fromParent=findParent(from);
        int toParent=findParent(to);
        if(toParent==fromParent) return false;
        Parent[toParent]=fromParent;
        return true;
    }

    private static int findParent(int from) {
        if(from==Parent[from]) return from;
        return Parent[from]=findParent(Parent[from]);
    }
    private static void makeSubset() {
        for (int i = 0; i < N; i++) {
            Parent[i]=i;
        }
    }
    private static void combi(long[][] map, int start, int cnt) {
        if(cnt==2){
            double weight=(Math.pow(Math.abs(map[subset[0]][0]-map[subset[1]][0]),2)+
                    Math.pow(Math.abs(map[subset[0]][1]-map[subset[1]][1]),2))*
                    E;
            list.add(new Edge(subset[0],subset[1],weight));
            return;
        }
        for (int i = start; i < N; i++) {
            subset[cnt]=i;
            combi(map,i+1,cnt+1);
        }

    }
}