[BOJ/Java] 1981. 배열에서 이동

📌 [BOJ/Java] 1981. 배열에서 이동

• 문제 링크

---

💡 문제 해석

N × N 크기의 2차원 배열이 주어진다.
왼쪽 상단 (0,0)에서 시작하여 오른쪽 하단 (N-1, N-1)까지 이동하는 경로를 찾아야 한다.

🔹 이동 조건

• 상하좌우 이동 가능
• 이동 중 최소값과 최대값의 차이(max - min)가 최소가 되어야 한다.

✅ 목표:
이동 경로에서의 최소값과 최대값의 차이를 최소화하는 값을 구하는 것!

---

📝 풀이 과정

1️⃣ 이분 탐색 + BFS 활용

✔ 이분 탐색의 범위:

• 배열의 값이 0 ~ 200이므로 최소값을 설정할 수 있는 범위를 이분 탐색
• 최소값을 low, 최대값을 high로 두고 탐색

✔ BFS로 경로 탐색:

• low부터 low + 최소 차이를 만족하는 값들을 BFS로 탐색
• 이동 가능하면 mid 값을 줄이고, 불가능하면 늘린다

---

💻 코드 (Java)

import java.util.*;

public class Main {
    static int N;
    static int[][] grid;
    static int minVal = 200, maxVal = 0;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        grid = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                grid[i][j] = sc.nextInt();
                minVal = Math.min(minVal, grid[i][j]);
                maxVal = Math.max(maxVal, grid[i][j]);
            }
        }

        System.out.println(binarySearch());
    }

    static int binarySearch() {
        int left = 0, right = maxVal - minVal;
        int result = right;

        while (left <= right) {
            int mid = (left + right) / 2;

            boolean possible = false;
            for (int minNum = minVal; minNum + mid <= maxVal; minNum++) {
                if (bfs(minNum, minNum + mid)) {
                    possible = true;
                    break;
                }
            }

            if (possible) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }

    static boolean bfs(int minLimit, int maxLimit) {
        if (grid[0][0] < minLimit || grid[0][0] > maxLimit) return false;

        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N][N];
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1];

            if (x == N - 1 && y == N - 1) return true;

            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[nx][ny]) {
                    int nextVal = grid[nx][ny];
                    if (nextVal >= minLimit && nextVal <= maxLimit) {
                        queue.offer(new int[]{nx, ny});
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        return false;
    }
}

---

⏱ 시간 복잡도 분석

• 이분 탐색 범위: 0 ~ 200 (최대 200번 반복)
• BFS 탐색: N × N 탐색 (O(N^2))
• 최악의 경우 200 × N^2 → 200 × 100^2 = 2,000,000 (충분히 가능)

---

🧐 느낀 점

🌟 이분 탐색과 BFS를 결합한 문제였다.
➡️ 이분 탐색으로 최소-최대 범위를 조정하고, BFS로 탐색 가능 여부를 판별하는 방식이 핵심이었다.
➡️ 평소에 이분 탐색을 단순한 정렬 문제에서만 사용했는데, 범위를 탐색하는 데도 적용할 수 있다는 점이 신기했다!

🔍 디테일한 부분에서 실수하기 쉬웠다.
✅ 최소값(minLimit)부터 최대값(maxLimit)까지의 범위를 조정하는 방식이 익숙하지 않아 시간이 걸렸다.
✅ BFS 탐색 시, 초기값이 범위를 벗어나면 즉시 false 처리하는 것이 중요했다.

🚀 이런 유형의 문제를 많이 연습하면 좋을 것 같다! 😊