[Programmers/Level 4] 지형 이동(Java)

문제 링크

프로그래머스

 

문제

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 이하인 자연수입니다.

 

예제 입력 1

4
1 4 8 10
5 5 5 5
10 10 10 10
10 10 10 20
3

예제 출력 1

15

예제 입력 2

4
10 11 10 11
2 21 20 10
1 20 21 11
2 1 2 1
1

예제 출력 2

18

 

제한사항

입출력 예 #1

각 칸의 높이는 다음과 같으며, 높이차가 3 이하인 경우 사다리 없이 이동이 가능합니다.

위 그림에서 사다리를 이용하지 않고 이동 가능한 범위는 같은 색으로 칠해져 있습니다. 예를 들어 (1행 2열) 높이 4인 칸에서 (1행 3열) 높이 8인 칸으로 직접 이동할 수는 없지만, 높이가 5인 칸을 이용하면 사다리를 사용하지 않고 이동할 수 있습니다.

따라서 다음과 같이 사다리 두 개만 설치하면 모든 칸을 방문할 수 있고 최소 비용은 15가 됩니다.

• 높이 5인 칸 → 높이 10인 칸 : 비용 5
• 높이 10인 칸 → 높이 20인 칸 : 비용 10

 

입출력 예 #2

각 칸의 높이는 다음과 같으며, 높이차가 1 이하인 경우 사다리 없이 이동이 가능합니다.

위 그림과 같이 (2행 1열) → (1행 1열), (1행 2열) → (2행 2열) 두 곳에 사다리를 설치하면 설치비용이 18로 최소가 됩니다.

 

알고리즘 분류

• 크루스칼 알고리즘
• 그래프 탐색

 

풀이

먼저 구역을 나누는데, 사다리를 타지 않고도 도달할 수 있으면 해당 칸은 같은 구역이라는 뜻이다.

BFS를 사용해서 구역을 나눈다.

그 다음 각 칸마다, 상하좌우로 다른 구역 칸과 인접해 있다면 해당 칸으로 이동하기 위해 필요한 비용을 구하고, 현재 구역을 From, 다음 구역을 To, 사다리 비용을 Cost로 하여 간선을 만든다.

간선을 다 만들었다면 Cost를 기준으로 오름차순 정렬을 하고, 크루스칼 알고리즘으로 MST를 구한다.

이 때 모든 구역을 이동해야 하므로 MST를 만들고 모든 구역이 이어졌는지는 확인할 필요는 없다.

MST를 만들어가면서 누적된 비용이 우리가 구하는 사다리 설치 비용의 최솟값이 된다.

 

코드

import java.util.*;

class Solution {
    
    private class Position {
        
        int Y, X;
        
        public Position(int Y, int X) {
            this.Y = Y;
            this.X = X;
        }
        
    }
    
    private class Edge implements Comparable<Edge> {
        
        int From, To, Cost;
        
        public Edge(int From, int To, int Cost) {
            this.From = From;
            this.To = To;
            this.Cost = Cost;
        }
        
        @Override
        public int compareTo(Edge e) {
            return this.Cost - e.Cost;
        }
        
    }
    
    private int N;
    private int[][] visited;
    private int sector = 1;
    private int[] moveY = { -1,0,1,0 };
    private int[] moveX = { 0,-1,0,1 };
    private List<Edge> edges = new ArrayList<>();
    private int[] parents;
    private int Answer = 0;
    
    private void bfs(int Y, int X, int[][] land, int height) {
        Queue<Position> queue = new LinkedList<>();
        queue.add(new Position(Y, X));
        visited[Y][X] = sector;
        
        while (!queue.isEmpty()) {
            Position now = queue.poll();
            int nowY = now.Y;
            int nowX = now.X;
            
            for (int i = 0; i < 4; i++) {
                int nextY = nowY + moveY[i];
                int nextX = nowX + moveX[i];
                if ((nextY >= 0) && (nextY < N) && (nextX >= 0) && (nextX < N) && (visited[nextY][nextX] == 0) && (Math.abs(land[nowY][nowX] - land[nextY][nextX]) <= height)) {
                    queue.add(new Position(nextY, nextX));
                    visited[nextY][nextX] = sector;
                }
            }
        }
    }
    
    private int findParent(int X) {
        if (parents[X] == X) {
            return X;
        }
        
        return parents[X] = findParent(parents[X]);
    }
    
    private void unionGroup(int X, int Y) {
        int PX = findParent(X);
        int PY = findParent(Y);
        
        if (PX < PY) {
            parents[PY] = PX;
        } else {
            parents[PX] = PY;
        }
    }
    
    public int solution(int[][] land, int height) {
        N = land.length;
        visited = new int[N][N];
        
        // 구역 나누기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (visited[i][j] == 0) {
                    bfs(i, j, land, height);
                    sector++;
                }
            }
        }
        
        // 구역 간 간선 놓기, Cost는 사다리 비용임
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int Y = i;
                int X = j;
                for (int k = 0; k < 4; k++) {
                    int nextY = Y + moveY[k];
                    int nextX = X + moveX[k];
                    if ((nextY < 0) || (nextY >= N) || (nextX < 0) || (nextX >= N)) continue;
                    if (visited[Y][X] == visited[nextY][nextX]) continue;
                    int Cost = Math.abs(land[Y][X] - land[nextY][nextX]);
                    edges.add(new Edge(visited[Y][X], visited[nextY][nextX], Cost));
                }
            }
        }
        
        Collections.sort(edges);
        
        parents = new int[sector];
        for (int i = 0; i < sector; i++) {
            parents[i] = i;
        }
        
        // MST
        for (int i = 0; i < edges.size(); i++) {
            int From = edges.get(i).From;
            int To = edges.get(i).To;
            int Cost = edges.get(i).Cost;
            if (findParent(From) != findParent(To)) {
                unionGroup(From, To);
                Answer += Cost;
            }
        }
        
        return Answer;
    }
    
}