[백준]22116: 창영이와의 퇴근 - JAVA

[백준]22116: 창영이와의 퇴근

풀이

🪑 단순 BFS라고 착각할 수 있으나 BFS는 거들 뿐,, 핵심 로직은 이분탐색을 사용해야 하는 문제이다!

 

📝 문제를 정리해 보자!

• 1, 1 -> N, N으로 이동한다. (나는 편의를 위해 0, 0 -> N-1, N-1로 생각해 주었다.)
• 상, 하, 좌, 우로 한 칸씩 이동한다.
• 인접 격자 사이의 높이차를 경사라고 할 때 지날 수 있는 최대 경사의 최솟값을 구한다.

 

📌 최대 경사의 최솟값! 이런 문제 유형은 이분탐색 유형이다. 바로 이분탐색으로 풀어야 겠다고 생각했다.

문제 조건에서 경사 높이의 범위를 보면, 1 에서 1000000000사이인걸 알 수 있다. 이 범위의 값을 이분탐색 해 준다. 

 

 

🔧 문제 구현 과정을 생각해 보자.

1. 격자의 정보를 입력 받는다.
2. 구해야 하는 값인 경사의 높이 차를 기준 값으로 두고 이분탐색을 한다.
3. BFS탐색을 통해 기준 값 만큼의 높이차를 허용하여 0,0 -> N-1,N-1에 도달할 수 있는지 확인한다.

 

🔹 격자의 정보를 입력 받는다.

- 이때 격자 높이의 최소, 최대값을 저장해 주었다.

- 이 값을 이분탐색할때 범위 값으로 사용 할 것이다.

 

🔹 경사의 높이 차를 기준 값으로 두고 이분탐색을 한다.

- left 값은 최소 높이 차인 0, right 값은 최대 높이차인 격자 정보를 입력 받을때 저장해 두었던 max - min값으로 설정해 주었다.

- 탐색을 하는 기준값은 경사의 높이 차이가 된다.

 

🔹 BFS탐색을 통해 기준 값 만큼의 높이차를 허용하여 0,0 -> n-1,n-1에 도달할 수 있는지 확인한다.

- mid 만큼의 높이 차를 허용할 때, 0,0에서 n-1, n-1까지 도달할 수 있다면 더 작은 높이 차를 가지는 부분을 확인한다.

- mid 만큼의 높이 차를 허용할 때, n-1까지 도달할 수 없다면 더 큰 높이차를 가지는 부분을 확인한다.

 

코드

import java.util.*;
 
public class Main {
 
    static int n;
    static int[][] board;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {-1, 0, 1, 0};
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        //입력
        n = scan.nextInt();
        board = new int[n][n];
        int min = Integer.MAX_VALUE;
        int max = -1;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                board[i][j] = scan.nextInt();
                min = Math.min(min, board[i][j]);
                max = Math.max(max, board[i][j]);
            }
        }
        //입력 끝   
    
        int left = 0;
        int right = max - min;
        while(left <= right) {
            int mid = (left + right) / 2;
 
            if(can_reach(mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(left);
    }
 
    public static boolean can_reach(int mid) {
        Queue<Node> q = new LinkedList<>();
        boolean[][] visited = new boolean[n][n];
 
        q.offer(new Node(0, 0));
        visited[0][0] = true;
 
        while(!q.isEmpty()) {
            Node current = q.poll();
 
            if(current.x == n - 1 && current.y == n - 1) return true;
            for(int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
 
                if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                if(visited[nx][ny] || Math.abs(board[nx][ny] - board[current.x][current.y]) > mid) continue;
                visited[nx][ny] = true;
                q.offer(new Node(nx, ny));
            }
        }
        return false;
    }
 
    public static class Node {
        int x;
        int y;
 
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}