[Code Tree] 높이 차를 최소화 하기

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-minimize-the-height-difference/description

높이 차를 최소화 하기 설명 | 코드트리

 

풀이

결론부터 말하자면 BFS와 Parametric Search를 활용하여 해결할 수 있는 문제이다.

 

이 문제를 풀기 위해 떠올렸던 사고 방식들을 순서대로 정리해보려고 한다.

 

첫 번째 방식 : Back Tracking + Parametric Search

첫 번째 떠올린 방식은 Back Tracking 방식과 Parametric Search를 활용한 방식이다.

 

우선 Parametric Search를 활용하기 위해서는 조건이 필요하다.

 

바로 어떠한 값이 조건을 만족한다면 그보다 큰 값 혹은 작은 값들 또한 모두 조건을 만족한다는 조건이 필요하다.

 

문제를 다시 보자.

 

최소 높이와 최대 높이 차이가 X 일 때, 목적지로 이동이 가능하다면 최소 높이와 최대 높이 차이가 X보다 크다면 무조건 만족한다는 것을 알 수 있다.

 

즉, 이 문제는 Parametric Search를 적용할 수 있는 문제이다.

 

높이가 최소 1, 최대 500이므로 높이 차이 또한 최대 499가 가능하다.

 

여기에 이진 탐색을 적용하면 약 9번 탐색을 할 수 있다.

 

이제 이 높이 차이를 활용해서 목적지에 도달할 수 있는지 확인해야 한다.

 

처음 떠올린 방식은 Back Tracking이었다.

 

지금까지 지나온 칸들의 최소 높이와 최대 높이를 계속 저장하면서 Back Tracking을 적용하는 방식이다.

 

하지만 이 방식의 시간이 너무 오래 걸린다는 점이다.

 

일반적인 DFS, BFS 같은 경우 이미 방문한 칸을 다시 방문하지 않는 방식으로 시간 복잡도를 줄인다.

 

하지만 Back Tracking을 적용하게 되면 이미 방문한 칸 또한 방문해야 한다.

 

특정한 칸에 도달하기 위한 경로가 두 개 있고, 첫 번째 경우는 최소 높이 5, 최대 높이 10, 두 번째 경우는 최소 높이 1, 최대 높이 6이라고 가정하자.

 

그리고 그 칸에서 갈 수 있는 모든 칸의 높이가 9라고 해보자.

 

이 경우 1번을 선택해야 높이 차이를 줄일 수 있다는 것을 알 수 있다.

 

그리고 이를 알아내려면 두 가지 경우에 대해서 모두 고려해야 하기 때문에 이미 방문한 칸을 다시 한 번 방문해야 하는 문제가 생긴다.

 

이 방식으로는 시간 초과가 발생한다.

 

두 번째 방식 : BFS + Parametric Search

첫 번째 방식은 시간이 너무 오래 걸린다.

 

두 번째 떠올린 방식은 BFS와 Parametric Search를 활용하는 방식이다.

 

여기서 중요한 점은 BFS를 진행할 때, 최대 높이와 최소 높이 차이를 이용하지 않고 최대 높이와 최소 높이 값 자체를 이용하는 것이다.

 

이러면 Back Tracking을 사용하지 않아도 된다.

 

단순히 최소 높이와 최대 높이 범위를 벗어나는 칸은 방문하지 않아도 되기 때문에 이미 방문한 칸을 방문하지 않아도 된다.

 

물론 Parametric Search를 적용하기 위해서는 최대 높이와 최소 높이 차이 값을 활용해야 하는데 이를 위해서 해당 차이가 가능한 모든 (최소 높이, 최대 높이) 쌍에 대해서 BFS를 진행해야 한다.

 

예를 들어 최소 높이, 최대 높이 차이가 h라고 한다면 (500-h)번 BFS를 수행해야 한다.

 

즉, 최대 높이와 최소 높이 차이 값이 h일 때, 목적지 도달 가능 여부를 판단하기 위한 시간 복잡도는 O(H x 5 x M x N) = O(HMN)이다.

 

또한 대략 500번에 대한 이진 탐색을 수행하면 약 9번을 수행하게 되므로 총 시간 복잡도는 O(log H) x O(HMN)가 된다.

 

최악의 경우 log(500) x 5 x 500 x 100 x 100 대략 2억 2천만 연산을 수행해야 한다.

 

보통 1억 번 연산을 수행하는데 1초가 걸리므로 문제 제한 시간인 5초 안에 넉넉히 통과할 수 있다.

 

코드

/*
    1. 최대 높이 최소 높이 차이가 주어질 때, 이게 가능한지 반환
    최대 높이와 최소 높이 차이가 주어지면 가능한 모든 경우의 수를 BFS로 탐색한다.
    정해진 최소 높이와 최대 높이 사이의 칸만 탐색하여 도착점에 도달 할 수 있는지 판단
    시간 복잡도 : O(H x 5 x M x N)

    2. 최대 높이 최소 높이 차이의 경우 이진 탐색으로 진행하여 1번을 실행한다.
    시간 복잡도 : O(log H) x O(HMN)

    최악의 경우 log(500) x 5 x 500 x 100 x 100 대략 2억 2천만
    시간 제한이 5초이기 때문에 넉넉히 통과할 수 있다.
*/
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
public class Main {
    public static int[][] board;
    public static int[] dx = {0, 0, 1, -1};
    public static int[] dy = {1, -1, 0, 0};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        board = new int[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                board[i][j] = sc.nextInt();
        
        // 이진 탐색 시작
        int left = 0;
        int right = 500;
        int res = 501;
        while (left <= right){
            int mid = (left+right)/2;
            if (isPossibleDifference(mid)){
                res = Math.min(res, mid);
                // 가능하면 범위를 좁혀보기
                right = mid-1;
            }
            // 불가능하면 범위를 넓혀보기
            else{
                left = mid+1;
            }
        }
        System.out.println(res);
    }
    // 해당 차이를 유지하면서 목표 지점까지 도달 가능 여부
    public static boolean isPossibleDifference(int difference){
        for (int minHeight=1; minHeight<=500-difference; minHeight++){
            // 한 번이라도 도달하면 가능
            if (BFS(minHeight, minHeight+difference)){
                return true;
            }
        }
        // 한 번도 도달하지 못 했다면 불가능
        return false;
    }
    
    // 최소 높이, 최대 높이를 유지하면서 탐색 가능한지
    public static boolean BFS(int minHeight, int maxHeight){
        // 만약 출발점부터 안 되면 false 반환
        if (board[0][0] < minHeight || board[0][0] > maxHeight){
            return false;
        }
        boolean[][] visited = new boolean[board.length][board[0].length];
        
        // 첫 번째 점부터 큐에 넣기
        Queue<Pair> queue = new LinkedList();
        queue.add(new Pair(0, 0));
        visited[0][0] = true;

        // 큐가 빌 때까지 반복
        while(!queue.isEmpty()){
            Pair pair = queue.remove();
            int cx = pair.x;
            int cy = pair.y;
            for (int i=0; i<4; i++){
                int nx = cx+dx[i];
                int ny = cy+dy[i];
                
                // 범위 벗어나먼 스킵
                if (nx<0 || nx>=board.length || ny<0 || ny>=board[0].length){
                    continue;
                }

                // 방문했으면 스킵
                if (visited[nx][ny]){
                    continue;
                }

                // 높이 범위 벗어나면 스킵
                if (board[nx][ny] < minHeight || board[nx][ny] > maxHeight){
                    continue;
                }

                // 만약 도달했으면 true 반환
                if (nx == board.length-1 && ny == board[0].length-1){
                    return true;
                }
                // 큐에 넣기
                queue.add(new Pair(nx, ny));
                visited[nx][ny] = true;
            }
        }
        // 큐가 빌 때까지 도달 못 했으면 false 반환
        return false;
    }
}
class Pair{
    public int x;
    public int y;
    public Pair(int x, int y){
        this.x = x;
        this.y = y;
    }
}