250x250
Notice
Recent Posts
Recent Comments
Link
«   2024/04   »
일 월 화 수 목 금 토
1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30
Tags more
Archives
Today
Total
관리 메뉴

막내의 막무가내 프로그래밍 & 일상

[알고리즘] 백준 2887 행성 터널 -최소신장트리- 자바 본문

알고리즘/유니온파인드, 최소신장트리(크루스칼)

[알고리즘] 백준 2887 행성 터널 -최소신장트리- 자바

막무가내막내 2020. 12. 26. 21:07
728x90

www.acmicpc.net/problem/2887

 

2887번: 행성 터널

첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이

www.acmicpc.net

 

백준 최소신장트리 문제인 행성 터널 문제를 풀어봤습니다. ㅎㅎ 

처음에 평소대로 푼 후 제출을 하였는데 메모리 초과가 일어났습니다. 

//모든 행성 관계 연결(엣지 초기화)
        for (int i = 0; i < N - 1; i++) {
            Space space = spaces[i];
            for (int j = i + 1; j < N; j++) {
                Space space2 = spaces[j];
                int weight = Math.min(Math.abs(space.x - space2.x), Math.min(Math.abs(space.y - space2.y), Math.abs(space.z - space2.z)));
                spaceList.add(new Space(i, j, 0, weight));
            }
        }

연결할 엣지들을 리스트에 추가해주는 코드인데 N이 10^9 이나 되는데 N^2 개의 데이터를 리스트에 넣는 꼴이니 메모리초과가 일어나구나 하고

밑과 같이 코드를 바꿔주었습니다.

 

 

 //모든 행성 관계 연결(엣지 초기화)
        for (int i = 0; i < N - 1; i++) {
            Space space = spaces[i];
            int minX = 0; //메모리초과 방지하기 위해 최소비용만 리스트에 넣어줌
            int minY = 0;
            int minWeight = Integer.MAX_VALUE;
            for (int j = i + 1; j < N; j++) {
                Space space2 = spaces[j];
                int weight = Math.min(Math.abs(space.x - space2.x), Math.min(Math.abs(space.y - space2.y), Math.abs(space.z - space2.z)));
                if (minWeight > weight) {
                    minX = i;
                    minY = j;
                    minWeight = weight;
                }
            }
            spaceList.add(new Space(minX, minY, 0, minWeight));
        }

하지만 이 코드는 시간초과가 일어났습니다. 원인은 역시 N^2 의 시간복잡도 때문이겠죠..

계속 생각하다가 어떻게 효율적으로 짤 지 잘 생각이 안나서 다른 블로그를 참고했는데 다들 시간초과가 나셨던 분들이 많았던 것 같고 x, y, z 좌표 정렬을 통해 반복문을 한번만 돌게 처리하여 시간초과 문제를 해결하는 것을 보았습니다.

 

 

밑 코드가 변경된 코드입니다. 개념을 알았으니 다시 코드를 짜서 통과하게 되었습니다.

//x, y, z 각 좌표로 정렬된 3개의 리스트 생성
        List<Space> xList = new ArrayList<>(Arrays.asList(spaces));
        xList.sort((o1, o2) -> o1.x - o2.x);
        List<Space> yList = new ArrayList<>(Arrays.asList(spaces));
        yList.sort((o1, o2) -> o1.y - o2.y);
        List<Space> zList = new ArrayList<>(Arrays.asList(spaces));
        zList.sort((o1, o2) -> o1.z - o2.z);
        //모든 행성 관계 연결(엣지 초기화)
        PriorityQueue<Edge> queue = new PriorityQueue<>();
        for (int i = 0; i < N - 1; i++) { 
            Space space1 = xList.get(i);
            Space space2 = xList.get(i + 1);
            queue.offer(new Edge(space1.num, space2.num, Math.min(Math.abs(space1.x - space2.x), Math.min(Math.abs(space1.y - space2.y), Math.abs(space1.z - space2.z)))));
            space1 = yList.get(i);
            space2 = yList.get(i + 1);
            queue.offer(new Edge(space1.num, space2.num, Math.min(Math.abs(space1.x - space2.x), Math.min(Math.abs(space1.y - space2.y), Math.abs(space1.z - space2.z)))));
            space1 = zList.get(i);
            space2 = zList.get(i + 1);
            queue.offer(new Edge(space1.num, space2.num, Math.min(Math.abs(space1.x - space2.x), Math.min(Math.abs(space1.y - space2.y), Math.abs(space1.z - space2.z)))));
        }

평소에 Edge클래스를 따로 안만들고 하나의 객체(클래스)로 통합해서 처리를 하는 경우가 많은데 여기서는 그렇게 하면 햇갈리기 때문에 Space, Edge 두 개의 클래스를 만들어 해결했습니다. (솔직히 이게 가독성이 당연히 더 좋겠죠 앞으로도 이렇게 하기로..)

 

 

다음은 시행착오를 겪었던 코드들입니다.

 

 

[메모리 초과난 코드]

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

class Main {
    private static int N; //행성 개수
    private static Space[] spaces;
    private static List<Space> spaceList = new ArrayList<>();
    private static int[] parent;
    private static int answer = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        parent = new int[N];
        spaces = new Space[N];
        for (int i = 0; i < N; i++) {
            parent[i] = i;
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            spaces[i] = new Space(x, y, z, 0);
        }
        //모든 행성 관계 연결(엣지 초기화)
        for (int i = 0; i < N - 1; i++) {
            Space space = spaces[i];
            for (int j = i + 1; j < N; j++) {
                Space space2 = spaces[j];
                int weight = Math.min(Math.abs(space.x - space2.x), Math.min(Math.abs(space.y - space2.y), Math.abs(space.z - space2.z)));
                spaceList.add(new Space(i, j, 0, weight));
            }
        }
        //최소비용 오름차순 정렬
        Collections.sort(spaceList);
        //탐색 및 연결
        for (Space space : spaceList) {
            if (!isSameParent(space.x, space.y)) {
                answer += space.weight;
                union(space.x, space.y);
            }
        }
        System.out.println(answer);
    }

    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a > b) parent[a] = b;
        else parent[b] = a;
    }

    private static int find(int a) {
        if (parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }

    private static boolean isSameParent(int a, int b) {
        return find(a) == find(b);
    }

    static class Space implements Comparable<Space> {
        int x;
        int y;
        int z;
        int weight;

        Space(int x, int y, int z, int weight) {
            this.x = x;
            this.y = y;
            this.z = z;
            this.weight = weight;
        }

        @Override
        public int compareTo(Space o) {
            return weight - o.weight;
        }
    }
}

 

 

 

 

[시간초과난 코드]

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

class Main {
    private static int N; //행성 개수
    private static Space[] spaces;
    private static List<Space> spaceList = new ArrayList<>();
    private static int[] parent;
    private static int answer = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        parent = new int[N];
        spaces = new Space[N];
        for (int i = 0; i < N; i++) {
            parent[i] = i;
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            spaces[i] = new Space(x, y, z, 0);
        }
        //모든 행성 관계 연결(엣지 초기화)
        for (int i = 0; i < N - 1; i++) {
            Space space = spaces[i];
            int minX = 0; //메모리초과 방지하기 위해 최소비용만 리스트에 넣어줌
            int minY = 0;
            int minWeight = Integer.MAX_VALUE;
            for (int j = i + 1; j < N; j++) {
                Space space2 = spaces[j];
                int weight = Math.min(Math.abs(space.x - space2.x), Math.min(Math.abs(space.y - space2.y), Math.abs(space.z - space2.z)));
                if (minWeight > weight) {
                    minX = i;
                    minY = j;
                    minWeight = weight;
                }
            }
            spaceList.add(new Space(minX, minY, 0, minWeight));
        }
        //최소비용 오름차순 정렬
        Collections.sort(spaceList);
        //탐색 및 연결
        for (Space space : spaceList) {
            if (!isSameParent(space.x, space.y)) {
                answer += space.weight;
                union(space.x, space.y);
            }
        }
        System.out.println(answer);
    }

    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a > b) parent[a] = b;
        else parent[b] = a;
    }

    private static int find(int a) {
        if (parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }

    private static boolean isSameParent(int a, int b) {
        return find(a) == find(b);
    }

    static class Space implements Comparable<Space> {
        int x;
        int y;
        int z;
        int weight;

        Space(int x, int y, int z, int weight) {
            this.x = x;
            this.y = y;
            this.z = z;
            this.weight = weight;
        }

        @Override
        public int compareTo(Space o) {
            return weight - o.weight;
        }
    }
}

 

 

 

[통과한 최종 코드]

import java.util.*;

class Main {
    private static int N; //행성 개수
    private static Space[] spaces;
    private static List<Space> spaceList = new ArrayList<>();
    private static int[] parent;
    private static long answer = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        parent = new int[N];
        spaces = new Space[N];
        for (int i = 0; i < N; i++) {
            parent[i] = i;
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            spaces[i] = new Space(i, x, y, z);
        }
        //x, y, z 각 좌표로 정렬된 3개의 리스트 생성
        List<Space> xList = new ArrayList<>(Arrays.asList(spaces));
        xList.sort((o1, o2) -> o1.x - o2.x);
        List<Space> yList = new ArrayList<>(Arrays.asList(spaces));
        yList.sort((o1, o2) -> o1.y - o2.y);
        List<Space> zList = new ArrayList<>(Arrays.asList(spaces));
        zList.sort((o1, o2) -> o1.z - o2.z);
        //모든 행성 관계 연결(엣지 초기화)
        PriorityQueue<Edge> queue = new PriorityQueue<>();
        for (int i = 0; i < N - 1; i++) { 
            Space space1 = xList.get(i);
            Space space2 = xList.get(i + 1);
            queue.offer(new Edge(space1.num, space2.num, Math.min(Math.abs(space1.x - space2.x), Math.min(Math.abs(space1.y - space2.y), Math.abs(space1.z - space2.z)))));
            space1 = yList.get(i);
            space2 = yList.get(i + 1);
            queue.offer(new Edge(space1.num, space2.num, Math.min(Math.abs(space1.x - space2.x), Math.min(Math.abs(space1.y - space2.y), Math.abs(space1.z - space2.z)))));
            space1 = zList.get(i);
            space2 = zList.get(i + 1);
            queue.offer(new Edge(space1.num, space2.num, Math.min(Math.abs(space1.x - space2.x), Math.min(Math.abs(space1.y - space2.y), Math.abs(space1.z - space2.z)))));
        }
        //탐색 및 연결
        while (!queue.isEmpty()) {
            Edge edge = queue.poll();
            if (!isSameParent(edge.vertex1, edge.vertex2)) {
                answer += edge.weight;
                union(edge.vertex1, edge.vertex2);
            }
        }
        System.out.println(answer);
    }

    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a > b) parent[a] = b;
        else parent[b] = a;
    }

    private static int find(int a) {
        if (parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }

    private static boolean isSameParent(int a, int b) {
        return find(a) == find(b);
    }

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

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

    private static class Edge implements Comparable<Edge> {
        int vertex1;
        int vertex2;
        int weight;

        public Edge(int vertex1, int vertex2, int weight) {
            this.vertex1 = vertex1;
            this.vertex2 = vertex2;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return weight - o.weight;
        }
    }
}

 

 

설명 참고 : steady-coding.tistory.com/117

 

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

문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

steady-coding.tistory.com

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!

728x90
저작자표시 동일조건

'알고리즘 > 유니온파인드, 최소신장트리(크루스칼)' 카테고리의 다른 글

[알고리즘] 프로그래머스 섬 연결하기 -그리디, 최소신장트리- 자바  (2) 2021.03.10
[알고리즘] 백준 10775 공항 -유니온파인드- 자바 코틀린  (0) 2021.02.27
[알고리즘] 백준 4195 친구 네트워크 -유니온 파인드- 자바  (0) 2020.12.21
[알고리즘] 백준 1774 우주신과의 교감 -최소신장트리- 자바  (0) 2020.12.11
[알고리즘] 백준 4386 별자리 만들기 -최소신장트리- 자바  (0) 2020.12.11
'알고리즘/유니온파인드, 최소신장트리(크루스칼)' Related Articles more
Comments