행성터널 [백준 2887][JAVA][골드 2][MST][Comparator]

 

[광고 누르면 오늘의 행운 상승!!]

https://www.acmicpc.net/problem/2887

2887번: 행성 터널

MST를 구하는 문제
너무 어려워서 블로그를 보고 풀었다. 
comparator를 람다식으로 사용하는 것을 보고 많이 배웠다.

1. 참고사항

- 노드(N)가 10만개 이므로 모든 간선을 이으면 시간초과가 발생한다. O(3*N*N)
- 간선을 최소화할 방법을 찾아야한다.
- 가중치를 낮은 순서대로 나열하고  abs(가중치1 - 가중치2) 를 차례로 구해나가면 최소 경로가 된다

2. 구현

- X Y Z 를 poss 배열에 담는다.
- poss 배열을 X,Y,Z기준으로 정렬하여 이전노드와 현재노드를 이어주고 
  Edge를 담는 list에 저장한다 ( i-1 , i , Math.abs(poss[i].x - poss[i-1].x))
- 만들어진 list를 거리순으로 정렬한다 (크루스칼을 이용하기 위함)
- 크루스칼 알고리즘을 사용하여 최소 경로를 이어가며 result에 값을 누적시킨다.
- 출력

3. 참고 사이트
https://sncap.tistory.com/m/921?category=845552

BOJ-2887 행성터널

4. 크루스칼 참고
https://toastfactory.tistory.com/185?category=848292

Kruskal 알고리즘 [크루스칼][MST][JAVA]

package Study8;

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

public class 행성터널 {
    static class Pos {
        int x, y, z, id;
        Pos(int x, int y, int z, int id) {
            this.x = x;
            this.y = y;
            this.z = z;
            this.id = id;
        }
    }
    static class Edge {
        int s, e, v;
        Edge(int s, int e, int v) {
            this.s = s;
            this.e = e;
            this.v = v;
        }
    }
    static int N;
    static Pos[] poss;
    static ArrayList<Edge> edges;
    static int[] p;
    
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("test.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        poss = new Pos[N];
        edges = new ArrayList<>();
        StringTokenizer st;
        
        
//        19 -1  19
//        14 -4  -1
//        11 -4  -5
//        10 -5  -15
//        -1 -15 -15
        
        for (int i = 0; i < N ; i++) {
            st = new StringTokenizer(br.readLine().trim(), " ");
            int X = Integer.parseInt(st.nextToken());
            int Y = Integer.parseInt(st.nextToken());
            int Z = Integer.parseInt(st.nextToken());
            poss[i] = new Pos(X, Y, Z, i);
        }

        // X 좌표 정렬
        Comparator<Pos> cmp = (o1,o2)-> o1.x-o2.x;
        Arrays.sort(poss,cmp);
        for (int i = 1; i <N ; i++) {
            edges.add(new Edge(poss[i-1].id, poss[i].id, Math.abs(poss[i].x-poss[i-1].x)));
        }

        // Y 좌표 정렬
        cmp = (o1,o2)-> o1.y-o2.y;
        Arrays.sort(poss,cmp);
        for (int i = 1; i <N ; i++) {
            edges.add(new Edge(poss[i-1].id, poss[i].id, Math.abs(poss[i].y-poss[i-1].y)));
        }

        // Z 좌표 정렬
        cmp = (o1,o2)-> o1.z-o2.z;
        Arrays.sort(poss,cmp);
        for (int i = 1; i <N ; i++) {
            edges.add(new Edge(poss[i-1].id, poss[i].id, Math.abs(poss[i].z-poss[i-1].z)));
        }
        
        // 간선 리스트 정렬
        Comparator<Edge> cmp2 = (o1,o2)-> o1.v-o2.v;
        Collections.sort(edges,cmp2);

        p = new int[N+1];
        for (int i = 1; i <= N ; i++) p[i] = i;
        
        // 크루스칼 (union find)을 이용한 mst
        long result=0;
        for (Edge ed:edges) {
            if(union(ed.s, ed.e)) {
                result += ed.v;
            }
        }
        System.out.println(result);
    }
    public static int find(int n) {
        if(n==p[n]) return n;
        return p[n] = find(p[n]);
    }
    public static boolean union(int a, int b) {
        a = find(a);
        b = find(b);
        if(a==b) return false;
        p[b] = a;
        return true;
    }
}