[프로그래머스] 지형 이동 - MST알고리즘(크루스칼알고리즘 사용)

문제

---

N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다.

이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있습니다. 이때, 사다리를 설치하는데 두 격자 칸의 높이차만큼 비용이 듭니다. 따라서, 최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하도록 해야 합니다. 설치할 수 있는 사다리 개수에 제한은 없으며, 설치한 사다리는 철거하지 않습니다.

각 격자칸의 높이가 담긴 2차원 배열 land와 이동 가능한 최대 높이차 height가 매개변수로 주어질 때, 모든 칸을 방문하기 위해 필요한 사다리 설치 비용의 최솟값을 return 하도록 solution 함수를 완성해주세요.

 

 

 

[제한사항]

• land는 N x N크기인 2차원 배열입니다.
• land의 최소 크기는 4 x 4, 최대 크기는 300 x 300입니다.
• land의 원소는 각 격자 칸의 높이를 나타냅니다.
• 격자 칸의 높이는 1 이상 10,000 이하인 자연수입니다.
• height는 1 이상 10,000 이하인 자연수입니다.

 

 

 

 

풀이

---

BFS, MST(최소신장트리) 알고리즘을 이용하여 푸는 문제다.

 

알고리즘 순서

1. BFS를 이용하여 사다리를 이용하지 않고 갈 수 있는 구간의 번호를 붙인다.
2. 구간이 다른 부분에서의 구간 번호와 차를 list에 저장한다.
3. list 를 land 비용을 기준으로 오름차순 정렬한다.
4. 크루스칼 알고리즘을 통해서 구간별 최소 비용을 구해서 더해준다. (Union-Find 사용)

 

위의 순서로 구해주면 된다.

코드의 필요한 설명은 주석으로 설명해 두었다.

import java.util.*;

class Solution {
    
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int[] parent;
    static int[][] visited;
    static int area;
    static List<vertex> list;
    
    static class point{
        int x;
        int y;
        
        point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    
    static class vertex implements Comparable<vertex>{
        int u;
        int v;
        int weight;
        
        vertex(int u, int v, int weight){
            this.u = u;
            this.v = v;
            this.weight = weight;
        }
        
        @Override
        public int compareTo(vertex v){
            return Integer.compare(this.weight, v.weight);
        }
    }
    
    public int solution(int[][] land, int height) {
        int answer = 0;
        visited = new int[land.length][land.length];
        
        for(int i = 0 ; i < land.length ; i++){
            Arrays.fill(visited[i], -1);
        }
        
        area = 0;
        //구간별 번호를 붙여준다.
        for(int i = 0 ; i < land.length ; i++){
            for(int j = 0 ; j < land.length ; j++){
                if(visited[i][j] < 0){                    
                    BFS(land, height, area++, j, i);
                }
            }
        }
        
        
        //구간 차를 list에 넣어준다.
        list = new ArrayList<>();
        for(int i = 0 ; i < land.length ; i++){
            for(int j = 0 ; j < land.length ; j++){
                for(int k = 0 ; k < 4; k++){
                    int nx = j + dx[k];
                    int ny = i + dy[k];
                    
                    if(nx < 0 || nx >= land.length || ny < 0 || ny >= land.length) { continue;}
                    if(visited[i][j] == visited[ny][nx]) { continue;}
                    
                    list.add(new vertex(visited[i][j], visited[ny][nx], Math.abs(land[i][j] - land[ny][nx])));
                }
            }
        }
        
        parent = new int[area];
        for(int i = 0 ; i < area ; i++){
            parent[i] = i;
        }
        //리스트를 구간 비용을 기준으로 오름차순정렬한다.
        Collections.sort(list);
        
        //union-find를 이용하여 최소신장트리를 완성한다.
        int count = 0;
        for(vertex Vertex : list){
            if(union(Vertex.u, Vertex.v)){
                answer += Vertex.weight;
                //모든 구간이 연결되면 반복문을 나가준다.
                if(++count == area -1){ break; }
            }
        }
        
        return answer;
    }
    
    static int find(int value){
        if(parent[value] == value){
            return value;
        }
        
        return parent[value] = find(parent[value]);
    }
    
    static boolean union(int a, int b){
        
        a = find(a);
        b = find(b);
        
        if(a == b){
            return false;
        }
        
        if(a > b){
            parent[a] = b;
        }
        else{
            parent[b] = a;
        }
        return true;
    }
    
    static void BFS(int[][] land, int height, int area, int x, int y){
        
        visited[y][x] = area;
        Queue<point> queue = new LinkedList<point>();
        queue.add(new point(x, y));
        
        while(!queue.isEmpty()){
            point now = queue.poll();
            
            int nowX = now.x;
            int nowY = now.y;
            
            for(int i = 0 ; i < 4; i++){
                int nx = nowX + dx[i];
                int ny = nowY + dy[i];
                
                if(nx < 0 || nx >= land.length || ny < 0 || ny >= land.length){ continue; }
                
                if(visited[ny][nx] >= 0) { continue; }
                
                if(Math.abs(land[nowY][nowX] - land[ny][nx]) > height) { continue; }
                
                visited[ny][nx] = area;
                queue.add(new point(nx, ny));
            }
        }
    }
}