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

문제 링크

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

풀이 과정

일반적인 bfs 탐색에 투 포인터를 활용하는 문제입니다.

while (start <= 200 && end <= 200) {
    if (bfs(start, end)) {
        answer = Math.min(answer, end - start);
        start++;
    } else {
        end++;
    }
}

0부터 200까지의 범위를 두고 start 와 end 변수의 값을 하나씩 증가시키며 bfs 탐색을 실행합니다. 진행하며 만나는 map 의 각 요소가 start~end 범위를 벗어나 bfs 탐색이 불가능하면 end 값을 1만큼 증가시키고 bfs를 다시 진행합니다. 현재 start~end 범위에서 bfs 탐색이 가능하다면, 더 적은 값의 최댓값과 최솟값의 차이를 만족시키는 지 확인해보기 위해 start를 1만큼 증가시킵니다.

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N;
    static int[][] map;
    static boolean[][] visit;
    static int[] di = {-1, 1, 0, 0};
    static int[] dj = {0, 0, -1, 1};

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

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                map[i][j] = sc.nextInt();

        int answer = 200, start = 0, end = 0;

        while (start <= 200 && end <= 200) {
            if (bfs(start, end)) {
                answer = Math.min(answer, end - start);
                start++;
            } else {
                end++;
            }
        }

        System.out.println(answer);
    }

    static boolean bfs(int start, int end) {
        if (map[0][0] < start || map[0][0] > end) return false;

        Queue<int[]> queue = new LinkedList<>();
        visit = new boolean[N][N];

        visit[0][0] = true;
        queue.add(new int[]{0, 0});

        while (!queue.isEmpty()) {
            int[] now = queue.poll();

            if (now[0] == N - 1 && now[1] == N - 1) return true;

            for (int d = 0; d < 4; d++) {
                int ni = now[0] + di[d];
                int nj = now[1] + dj[d];

                if (inRange(ni, nj) && !visit[ni][nj] && start <= map[ni][nj] && map[ni][nj] <= end) {
                    visit[ni][nj] = true;
                    queue.add(new int[]{ni, nj});
                }
            }
        }

        return false;
    }

    private static boolean inRange(int i, int j) {
        if (i < 0 || i > N - 1 || j < 0 || j > N - 1) return false;
        return true;
    }
}