[백준] 1981번 : 배열에서 이동 - 자바(JAVA)

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

1981번: 배열에서 이동

 

문제 해석

n x n 배열이 존재하고 배열의 (1,1)에서 (n, n)까지 이동하려고 합니다.

이동할 때는 상하좌우로 1칸씩 이동할 수 있습니다.

이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하세요

 

문제 풀이 전 설계

n의 범위는 최대 100 x 100으로 10,000입니다.

 

세 가지 풀이가 떠올랐습니다.

 

1. 파라메트릭 서치

배열의 각 수는 0보다 크거나 같고 200보다 작거나 같다

즉, 답이 올 수 있는 범위는 0,200이며 답이 올 수 있는 후보를  0~200 범위를 이진 탐색으로 탐색하면서 찾아본다.

 

2. 완전 탐색

진짜 모든 경우를 순회하면서 최대 최솟값을 기록한다.

 

3. 다익스트라 응용 - PQ 활용

상하좌우를 탐색하면서 최댓값 - 최솟값이 가장 작은 것을 우선순위로 탐색한다.

 

 

2번 풀이가 가장 비효율적이고 그다음이 1번 풀이 그다음이 3번 풀이일 것 같습니다.

 

가장 효율적일 것 같은 3번 풀이로 시도해 보겠습니다.

 

문제 풀이

결국에는 1번 풀이로 시도해야 합니다.

뭔가 3번 풀이가 계속될 듯 안될 듯해서 시도해봤지만 결국에는 반례가 존재했습니다.

반례

3
2 4 9
1 2 2
9 2 4

답: 2

 

결국 0~200 범위를 파라메틱 서치로 탐색합니다.

 

그리고 값의 차이가 gap만큼 나는 것은 알지만 시작 값과 끝 값을 알 수 없기 때문에 0~ board [0][0]까지 반복하면서 board [n-1][n-1]까지 도달할 수 있는지 검사합니다.

 

코드

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

public class Main_1981_배열에서이동 {

    static class Pos {
        int x, y;

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

    static int N;
    static int[][] board;
    static boolean[][] canMove;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static Queue<Pos> q = new LinkedList<>();

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        board = new int[N][N];
        canMove = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

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

    private static int parametric() {
        int left = 0;
        int right = 200;
        int mid, result = right;

        while (left <= right) {

            mid = (left + right) >> 1;

            if (isPossible(mid)) {
                result = Math.min(result, mid);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }

    private static boolean isPossible(int gap) {
        //이때 어떤 값의 차이가 mid인것만 알 뿐 시작값과 끝 값은 알 수 없기 때문에 for문을 반복하면서 ㅏㅁ색한다.
        for (int start = 0; start <= board[0][0]; start++) {
            init(start, start + gap);

            while (!q.isEmpty()) {
                Pos cur = q.poll();

                if (cur.x == N - 1 && cur.y == N - 1) {
                    return true;
                }

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

                    if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
                        if (canMove[nx][ny]) {
                            canMove[nx][ny] = false;
                            q.add(new Pos(nx, ny));
                        }
                    }
                }
            }
        }
        return false;
    }

    private static void init(int min, int max) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                canMove[i][j] = isTrue(i, j, min, max);
            }
        }

        q.clear(); // 큐클리어
        if (canMove[0][0]) {
            q.add(new Pos(0, 0));
        }
    }

    private static boolean isTrue(int r, int c, int min, int max) {
        return board[r][c] >= min && board[r][c] <= max;
    }

}