[BOJ2887] 행성 터널(최소신장트리,MST, 크루스칼 알고리즘)

 

 

---

문제 링크

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

2887번: 행성 터널

 

문제 풀이

- 크루스칼 알고리즘으로 풀이시 메모리 초과 발생

- 행성의 개수 N이 최대 10^5 일 때 2중 for문 순회하면서 cost 연산 후 edge 추가시 최대 10^5 * 10^5 (러프하게 해석, 중복 제외시 연산은 더 적음)이고,  Edge의 경우 class Edge {int from, int to, long cost} 로 정의시 (4byte * 2 + 8byte) 하나당 16byte 차지함 

- 결국 16 byte * 10^10  = 120Gbyte 정도 나와서 메모리 초과가 발생하는 거 였다. 

 

Point.

- 찾아본 결과 x 오름차순 정렬해서 각 행성에 대한 cost 비용을 구해서 edge 추가한다. (y, z도 마찬가지)

- 이렇게 될 경우 3N 의 Edge 정보만 가지고 크루스칼 알고리즘 수행가능 해짐 (30만 * 16byte = 4.8Mbyte)

- 크루스칼 알고리즘 시간복잡도 : O(ElogE) = O(30000log30000)

갈 길이 멀다.. 시야가 좁다..

 

# 예제 입력 
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

# 예제 출력
4

 

- 공식에 너무 매몰되어 있었는데, 굳이 2중 for문 돌 필요없이 축마다 오름차순 정렬해서 공식대로 가중치 구하면 간선의 정보를 쉽게 구할 수 있었다.
- 이미 오름차순 자체 만으로 MST 형태를 보이고 있기 때문에, 그 중에 가중치가 적은 거로만 구성하면 되는 거였다.

 

1) x 축 오름차순 정렬

-1
10
11
14
19

 

2) y축 오름차순 정렬

-15
-5
-5
-4
-1

 

3) z축 오름차순 정렬

-15
-15
-5
-1
19

 

4) cost 기준 오름차순으로 edges 정렬 결과 

- (1,2) 행성이 cost 0에 연결

- (3,4) 행성이 cost 0에 연결

- (2,3) 행성이 cost 1에 연결

- (4,5) 행성이 cost 3에 연결

[
   "Edge"{
      from=3,
      to=4,
      cost=0
   },
   "Edge"{
      from=1,
      to=2,
      cost=0
   },
   "Edge"{
      from=2,
      to=3,
      cost=1
   },
   "Edge"{
      from=2,
      to=3,
      cost=1
   },
   "Edge"{
      from=3,
      to=4,
      cost=3
   },
   "Edge"{
      from=4,
      to=5,
      cost=3
   },
   "Edge"{
      from=3,
      to=4,
      cost=4
   },
   "Edge"{
      from=4,
      to=5,
      cost=5
   },
   "Edge"{
      from=1,
      to=2,
      cost=10
   },
   "Edge"{
      from=2,
      to=3,
      cost=10
   },
   "Edge"{
      from=1,
      to=2,
      cost=11
   },
   "Edge"{
      from=4,
      to=5,
      cost=20
   }
]

 

참고. 느리더라도 꾸준하게 

https://steady-coding.tistory.com/117

[BOJ] 백준 2887번 : 행성 터널 (JAVA)

 

제출 코드

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

public class Main {
   static List<Edge> edges = new ArrayList<>();

    static int N;
    static int[] parent;

    static class Plant {
        int x;
        int y;
        int z;
        int num;

        public Plant(int num, int x, int y, int z) {
            this.num = num;
            this.x = x;
            this.y = y;
            this.z = z;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public int getZ() {
            return z;
        }
    }

    static class Edge implements Comparable<Edge> {
        int from;
        int to;
        long cost;

        public Edge(int from, int to, long cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge other) {
            if(cost < other.cost) return -1;
            else if(cost == other.cost) return 0;
            return 1;
        }
        
    }
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        Plant[] plants = new Plant[N + 1];
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());

            plants[i] = new Plant(i, x, y, z); // 행성 번호 i를 추가
        }

        Arrays.sort(plants, 1, N + 1, (a, b) -> a.x - b.x); // toIndex : exclusive
        for(int i = 1; i < N; i++) {
            long cost = Math.abs(plants[i].x - plants[i + 1].x);

            edges.add(new Edge(plants[i].num, plants[i + 1].num, cost));
        }

        Arrays.sort(plants, 1, N + 1, (a, b) -> a.y - b.y);
        for(int i = 1; i < N; i++) {
            long cost = Math.abs(plants[i].y - plants[i + 1].y);

            edges.add(new Edge(plants[i].num, plants[i + 1].num, cost));
        }

        Arrays.sort(plants, 1, N + 1, (a, b) -> a.z - b.z);
        for(int i = 1; i < N; i++) {
            long cost = Math.abs(plants[i].z - plants[i + 1].z);

            edges.add(new Edge(plants[i].num, plants[i + 1].num, cost));
        }

    }

    static int getParent(int idx) {
        if(parent[idx] == idx) return idx;

        return parent[idx] = getParent(parent[idx]);
    }

    static void union(int a, int b) {
        int parentA = getParent(a);
        int parentB = getParent(b);

        if(parentA < parentB) parent[parentB] = parentA;
        else parent[parentA] = parentB;
    }

    static boolean unionFind(int a, int b) {
        return getParent(a) == getParent(b);
    }

    static void kruskal() {
        Collections.sort(edges);

        parent = new int[N + 1];
        for(int i = 1; i <= N; i++) parent[i] = i;

        long cost = 0L;
        for(Edge edge : edges) {
            if(!unionFind(edge.from, edge.to)) {
                union(edge.from, edge.to);
                cost += edge.cost;
            }
        }

        System.out.println(cost);
    }

    public static void main(String[] args) throws Exception {
        input();
        kruskal();
    }
    
}