[백준 JAVA] 1981 : 배열에서 이동

[백준 1981] 배열에서 이동 : https://www.acmicpc.net/problem/1981

1981번: 배열에서 이동

---

문제 조건 정리

 

1. n×n짜리의 배열이 하나 있다.
2. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다.
3. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 거쳐서 이동하게 된다.
4. 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 프로그램을 작성하시오.

---

입력

 

1. 첫째 줄에 n(2 ≤ n ≤ 100)이 주어진다.
2. 다음 n개의 줄에는 배열이 주어진다.
3. 배열의 각 수는 0보다 크거나 같고, 200보다 작거나 같은 정수이다.

---

문제를 풀기 전

 

1. 모든 경로를 bfs로 검색하는 문제라면 플레티넘 문제일 수 없다고 생각함.
2. 정답 비율을 봤을 때 겪어보지 못한 무언가가 있다고 직감함.
3. 한참을 고민했지만, 떠오르지 않아서 알고리즘 분류 탭을 통해서 "이분탐색" 을 확인함.
4. 이분탐색으로 어떻게 풀어야할지 고민함.

---

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    // 입력된 map 탐색을 위한 위치를 저장하는 클래스
    private static class Pos {
        int row, col;

        public Pos(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int n;
    static int[][] map;
    static boolean[][] visited;


    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bufferedReader.readLine());

        map = new int[n][n];
        visited = new boolean[n][n];

        // 입력 중 최댓값, 최솟값를 저장할 변수 초기화
        int max = 0;
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(stringTokenizer.nextToken());

                // 최댓값 찾기
                if (map[i][j] > max) {
                    max = map[i][j];
                }
                // 최솟값 찾기
                if (map[i][j] < min) {
                    min = map[i][j];
                }
            }
        }

        /*********************************************
         *  int left = min
         *  int right = max
         *  위와 같이 초기화하면 해결할 수 없는 탐색 범위가 있음
         *  자세한 설명은 아래에 기재함
         *********************************************/
        int left = 0;
        int right = max - min;
        int mid;

        int startValue = map[0][0];
        int targetValue = map[n - 1][n - 1];
        int minGap = Math.abs(startValue - targetValue);

        int answer = Integer.MAX_VALUE;

        // 이진 탐색(이분 탐색) 시작
        while (left <= right) {
            mid = (left + right) / 2;

            // bfs 성공, 실패를 저장하는 변수
            boolean bfsSuccessCheck = false;

            /*****************************************************************************
             *  입력 값 중 최솟 값 -> min
             *  입력 값 중 최댓 값 -> max
             *  현재 mid 값으로 bfs 탐색이 가능한 범위를 찾음
             *  즉, bfs 탐색 범위의 시작을 찾음
             *  시작 지점(i)은 min ~ (max - mid)의 범위에서 가능함
             *  (max - mid)까지 가능한 이유는 입력 값 중에서 max를 넘어선 수가 없기 때문임
             *  풀어서 말하자면, (max - mid) ~ max 가 가장 마지막으로 올바른(효율적인) 탐색이 가능한 범위
             *****************************************************************************/
            for (int i = min; i <= max - mid; i++) {
            
                // 시작지점과 목표지점은 반드시 탐색 범위안에 포함되어야 함
                if (i <= startValue && startValue <= i + mid && i <= targetValue && targetValue <= i + mid) {

                    /*******************************************************
                     *  시작지점(0,0)과 목표지점(n-1,n-1)은 반드시 거쳐야 함
                     *  시작지점 값과 목표지점 값의 차이 -> minGap
                     *  거쳐간 수들 중 최소한의 차이, 즉 문제에서 요구하는 값 -> answer
                     *  answer >= minGap 을 만족해야 함.
                     *  answer = 탐색이 가능한 mid 중에서 가장 작은 mid
                     *  따라서, mid < minGap 은 절대로 bfs 탐색이 불가능
                     *  bfsSuccessCheck = false, 반복 break
                     *******************************************************/
                    if (mid < minGap) {
                        break;
                    }

                    // 현재 mid 값으로 bfs를 시작지점부터 목표지점까지 가능한지 저장
                    bfsSuccessCheck = bfs(i, i + mid);

                    // 가능했다면 현재 mid는 answer가 될 수 있음
                    // 더 이상 현재 mid로 탐색 할 필요 없음 -> 반복 break
                    if (bfsSuccessCheck) {
                        break;
                    }
                }
            }

            /*******************************************************
             *  해당 mid로 탐색이 가능했다면?
             *  answer 갱신 해두기
             *  mid 감소 도전(더 작은 mid로 탐색이 가능한지 알아보기 위해서)
             *  -> right = mid - 1
             *******************************************************/
            if (bfsSuccessCheck) {
                right = mid - 1;
                answer = Math.min(answer, mid);
            }

            /*******************************************************
             *  // 해당 mid로 탐색이 불가능했다면?
             *  mid 증가 필요
             *  -> left = mid + 1
             *******************************************************/
            else {
                left = mid + 1;
            }
        }

        // (left > right) -> while 문 탈출
        // 탐색 끝, 결과 출력
        System.out.println(answer);


    }

    private static boolean bfs(int rangeStartPoint, int rangeEndPoint) {
        // 각 bfs 탐색마다 visited 배열 초기화
        for (int i = 0; i < n; i++) {
            Arrays.fill(visited[i], false);
        }

        Queue<Pos> queue = new ArrayDeque<>();
        queue.offer(new Pos(0, 0));
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            Pos current = queue.poll();

            // 반복문 탈출 조건 (목표 지점 도착했다면?)
            if (current.row == n - 1 && current.col == n - 1) {
                return true;
            }

            for (int i = 0; i < 4; i++) {
                int nextRow = current.row + dx[i];
                int nextCol = current.col + dy[i];

                if (isSafe(nextRow, nextCol) && !visited[nextRow][nextCol]) {
                    int nextVal = map[nextRow][nextCol];

                    if (rangeStartPoint <= nextVal && nextVal <= rangeEndPoint) {
                        queue.offer(new Pos(nextRow, nextCol));
                        visited[nextRow][nextCol] = true;
                    }
                }
            }
        }

        // 해당 범위로는 목표 지점 도착 불가능했다면?
        return false;
    }

    // 올바른 범위인지 검사
    private static boolean isSafe(int nextRow, int nextCol) {
        return 0 <= nextRow && nextRow < n && 0 <= nextCol && nextCol < n;
    }
}

 

---

이진 탐색 (feat. GPT)

일반적으로 이진 탐색에서 left와 right는 탐색하고자 하는 범위를 정의합니다. 
이 범위는 찾고자 하는 값이 존재할 수 있는 최소값과 최대값 사이여야 합니다. 

(case 1) left = 0과 right = max - min으로 설정하는 경우는, 찾고자 하는 값(이 경우, 가능한 최소-최대 값의 차이)이 0부터 최대값과 최소값의 차이 사이에 존재할 것이라고 가정할 때 적합합니다. 

(case 2) left = min과 right = max로 설정하는 경우는, 문제가 최소값 또는 최대값 자체를 찾으려고 할 때 더 적합할 수 있습니다. 이는 값 자체를 찾는 경우에 사용됩니다. 

따라서, left = 0과 right = max - min으로 설정하는 것이 이 문제에서 더 적합하다고 볼 수 있습니다. 
이는 탐색 범위가 "가능한 최소-최대 값의 차이"임을 명확히 반영하기 때문입니다. 
이진 탐색의 핵심은 탐색 범위를 반으로 줄여가며, 조건을 만족하는 최적의 값을 찾는 것입니다. 
따라서, 시작 조건은 문제의 맥락과 구하려는 값의 특성을 잘 반영해야 하며, left와 right를 설정하는 방식은 이러한 요소들을 고려하여 결정되어야 합니다.

 

백준 기준으로 (case 2) left = min과 right = max를 통해서 문제를 풀려고 했을 때, 채점의 70% 이후에 "틀렸습니다" 를 확인했습니다.

 

1 1 1 3 1 1 1 2
3 3 1 3 1 2 1 2
1 1 1 1 1 2 1 2
3 3 3 3 3 3 1 2
1 1 1 3 3 2 1 2
1 2 1 1 1 1 1 2
1 3 3 3 3 2 2 2
1 1 1 1 1 1 1 1

 

위 반례를 통해서 문제를 발견했습니다.

 

left <= right 조건때문에 mid가 0이 될 수 없는 문제입니다.

 

이를 해결하기 위해서 (case 1) left = 0과 right = max - min 를 사용해서 mid가 0이 될 수 있도록 이진탐색 범위를 올바르게 수정했습니다.

---

문제를 풀고 난 후

 

오랜만에 문제와 기싸움을 했다.

문제를 두고 엄청나게 째려봤다.

 

주석이 길게 적힌 부분은 내가 문제를 풀면서 이해하기 힘들었던 파트를 최대한 쉽게 이해할 수 있도록 작성했다.

문제를 풀고 보니 나름 잘 풀었다고 생각이 든다.

 

 

혹시 코드의 주석과 풀이에서 문제가 있다면 지적해주세요!