[백준] 1981번 배열에서 이동

문제 설명

https://www.acmicpc.net/problem/1981

문제 풀이

• 이분탐색을 이용하여 풀이하였다.
• 이분탐색의 대상은 최댓값과 최솟값의 차이의 크기이다.
• 특정 차이에 대해 모든 가능한 최소, 최대값을 지정하고 BFS를 돌려
  - 가능하면 hi = mid (최댓값과 최솟값 차이를 더 작게)
  - 불가능하면 lo = mid (최댓값과 최솟값 차이를 더 크게)
• 단지 최댓값 최솟값 차이를 가지고 BFS를 돌려(최소, 최대를 지정해 줘야함) 많이 헤맸다..

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

class Main {
    public static BufferedWriter bw;
    public static BufferedReader br;
    public static int N;
    public static int maxValue = Integer.MIN_VALUE, minValue = Integer.MAX_VALUE;
    public static int[][] map;
    public static int[] dx = {0,0,1,-1};
    public static int[] dy = {1,-1,0,0};

    public static class Point{
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static boolean check(int min, int max) {
        Queue<Point> q = new ArrayDeque<>();
        boolean[][] chk = new boolean[N][N];
        chk[0][0] = true;
        q.add(new Point(0, 0));
        while(!q.isEmpty()) {
            Point cur = q.poll();
            if (cur.x == N - 1 && cur.y == N - 1)
                return true;
            for (int d = 0; d < 4; d++) {
                int X = cur.x + dx[d];
                int Y = cur.y + dy[d];
                if (X < 0 || Y < 0 || X >= N || Y >= N || chk[X][Y]) continue;
                if (map[X][Y] >= min && map[X][Y] <= max) {
                    chk[X][Y] = true;
                    q.add(new Point(X, Y));
                }
            }
        }
        return false;
    }

    public static int solve() {
        int lo = -1;
        int hi = maxValue - minValue + 1;
        while(lo + 1 < hi) {
            int mid = (lo + hi) / 2;
            boolean resultFlag = false;
            for (int i = minValue; i <= maxValue - mid; i++) {
                if (map[0][0] >= i && map[0][0] <= i + mid) {
                    if (check(i, i + mid)) {
                        resultFlag = true;
                        break;
                    }
                }
            }
            if (resultFlag) hi = mid;
            else lo = mid;
        }
        return hi;
    }

    //입력
    public static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                minValue = Math.min(minValue, map[i][j]);
                maxValue = Math.max(maxValue, map[i][j]);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        bw = new BufferedWriter(new OutputStreamWriter(System.out)) ;
        br = new BufferedReader(new InputStreamReader(System.in));
        input();
        bw.write(solve() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}