[SWEA : JAVA] 1251 하나로 (MST, Prim 알고리즘)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD 

SW Expert Academy

정리

1. 모든 섬을 관통할 수 있는 해저 터널 연결
2. 해저 터널은 두 섬을 선분으로 연결하며, 두 해저터널이 교차하더라도 연결되지 않은것이다.
3. 환경 부담금 : 환경 부담 세율(E) * 해저 터널 길이(L) 의 제곱
4. 총 환경 부담금을 최소로 하기

 

풀이

• 총 환경 부담금을 최소로 하기 위해서 하나의 섬에서 다른 섬으로 선분을 연결할 때마다 매번 가장 가까운 섬과 연결해야 한다.
• 모든 섬을 연결해야 하므로 MST(Minimum Spanning Tree)로 해결해야 한다.
• 각 섬들을 잇는 터널의 길이(L)의 제곱을 저장해야 한다.
• Prim 알고리즘 적용

 

public class s1251 {

    public static class Node implements Comparable<Node> {
        int num;
        long w;

        public Node(int num, long w) {
            this.num = num;
            this.w = w;
        }

        @Override
        public int compareTo(Node o) {
            return Long.compare(this.w, o.w);
        }

    }

    static List<Node>[] lists;
    static int N;
    static boolean[] visited;
    static double tax;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {

            // 섬의 갯수
            N = Integer.parseInt(br.readLine());
            Point[] island = new Point[N];
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            tax = Double.parseDouble(br.readLine());
            lists = new ArrayList[N];
            visited = new boolean[N];
            for(int i = 0 ; i<N; i++){
                lists[i] = new ArrayList<>();
                island[i] = new Point();
                // 각 섬의 x,y좌표 저장
                island[i].x = Integer.parseInt(st1.nextToken());
                island[i].y = Integer.parseInt(st2.nextToken());
            }

            for(int i = 0 ; i<N ; i++){
                for(int j= 0; j<N; j++){
                    if(i==j)continue;
                    int distX = Math.abs(island[i].x-island[j].x);
                    int distY = Math.abs(island[i].y-island[j].y);
                    // 각 노드별 터널의 길이(L)의 제곱 저장
                    lists[i].add(new Node(j, (long) distX * distX + (long) distY * distY));
                }
            }

            long answer = prim();
            System.out.println("#" + tc + " " + answer);
        }
    }

    private static long prim() {
        Queue<Node> q = new PriorityQueue<>();
        q.add(new Node(0, 0));
        long length = 0;
        int cnt = 0;
        while (!q.isEmpty()){
            Node cur = q.poll();
            if(visited[cur.num]) continue;
            visited[cur.num] = true;
            length+=cur.w;
            // 모든 섬 연결 완료
            if(++cnt==N)break;
            for(int i = 0; i<lists[cur.num].size(); i++){
                Node next = lists[cur.num].get(i);
                if(!visited[next.num]){
                    q.add(next);
                }
            }
        }
        // 세율 적용
        return Math.round(length*tax);
    }
}