[백준] 1981번 - 배열에서 이동 (java)

Baekjoon 1981 - 배열에서 이동 (클릭 시 이동)

문제

n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다.

이와 같이 이동하다 보면, 배열에서 몇 개의 수를 거쳐서 이동하게 된다. 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 프로그램을 작성하시오.

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	5820	1455	947	23.616%

입력

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

출력

첫째 줄에 (최대 - 최소)가 가장 작아질 때의 그 값을 출력한다.

풀이

1. 주어진 배열의 최솟값(min)과 최댓값(max)을 찾는다.

2. 이분탐색을 사용하게 되는데 정답이 min과 max의 중간값(mid)라고 가정하고 bfs를 수행 해 본다.

   2-1. 이 때 어떤 값의 차이만 알 뿐 시작값과 끝 값은 알 수 없으니 for문을 돌려서 될때까지 bfs를 해본다.

3. 성공적으로 탐색했다면 차이를 더 줄여본다. 실패했다면 차이를 늘려본다.

4. 성공할때마다 answer = Math.min(answer, mid)로 업데이트 한다.

5. 이분탐색이 끝나면 결과를 출력한다.

최종 소스코드

package BJ_Practice;

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

public class BJ_G1_1981_배열에서_이동 {

    static int N;
    static int[][] map;
    static boolean visited[][];
    static int[][] deltas = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int min = 1000, max = 0;
    static StringTokenizer st;

    static class RC {
        int r, c;

        public RC(int r, int c) {
            super();
            this.r = r;
            this.c = c;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                max = Math.max(max, map[i][j]);
                min = Math.min(min, map[i][j]);
            }
        }

        int start = 0;
        int end = max - min;
        int answer = 987654321;
        while (start <= end) {
            int mid = (start + end) / 2;
            boolean flag = false;

            for (int i = min; i <= max; i++) {        // 차이가 mid인 값을 싹 다 탐색
                if (i <= map[0][0] && map[0][0] <= i + mid)
                    if (flag = bfs(i, i + mid))    // 경로가 하나라도 있으면 true -> break
                        break;
            }
            if (flag) {
                end = mid - 1;
                answer = Math.min(answer, mid);    // 경로가 있으면 차이를 정답에 반영
            } else
                start = mid + 1;
        }
        System.out.println(answer);
    }

    static boolean bfs(int min, int max) {
        Queue<RC> queue = new LinkedList<>();
        queue.offer(new RC(0, 0));

        for (int i = 0; i < N ; i++) {
            Arrays.fill(visited[i], false);
        }

        visited[0][0] = true;

        while (!queue.isEmpty()) {
            RC curr = queue.poll();

            if (curr.r == N - 1 && curr.c == N - 1) {    // 목적지에 도달할 수 있으면 끝
                return true;
            }

            for (int i = 0; i < 4; i++) {
                int nr = curr.r + deltas[i][0];
                int nc = curr.c + deltas[i][1];

                if (isIn(nr, nc) && !visited[nr][nc] 
                    &&  min <= map[nr][nc] && map[nr][nc] <= max) {    //사이에 값 존재

                    queue.offer(new RC(nr, nc));
                    visited[nr][nc] = true;
                }
            }
        }

        return false;
    }

    static boolean isIn(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < N;
    }
}