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

문제 설명

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

문제 풀이

• BFS + 투포인터를 이용하여 풀이하였다.
• 단순 BFS로 풀이하여 모든 경우 수를 고려하는 경우 시간초과가 발생한다.
• 문제의 조건에서 나올 수 있는 최대값 - 최소값의 범위는 0~200이므로 (제한적인 경우의수) 특정 최소값, 최대값을 정해놓고 해당 값을 만족하는지 BFS를 진행시켜 확인해본다.
• 이때 최소값, 최대값을 2중 for문으로 구성하면 BFS를 200*200 번 진행 시켜야 하는 반면, 투포인터 알고리즘을 이용하면 200+200번만 진행하면 된다.

소스 코드 (JAVA)

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

public class Main {
    public static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static int INF = 987654321;
    public static int N;
    public static int[][] map = new int[100][100];
    public static boolean[][] chk = new boolean[100][100];
    public static int result = INF;
    public static int minVal = INF;
    public static int maxVal = -INF;
    public static int[] dx = {0,0,1,-1};
    public static int[] dy = {1,-1,0,0};
    public static Queue<Point> queue = new LinkedList<>();

    public static void clearChk() {
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                chk[i][j] = false;
    }

    public static boolean bfs(int L, int R) {
        if (map[0][0] < L || map[0][0] > R) return false;
        clearChk();
        queue.clear();
        queue.add(new Point(0,0));
        chk[0][0] = true;
        while(!queue.isEmpty()) {
            Point cur = queue.poll();
            //마지막 지점 도착한 경우
            if (cur.x == N-1 && cur.y == N-1) {
                return true;
            }
            for (int d = 0; d < 4; d++) {
                int X = cur.x + dx[d];
                int Y = cur.y + dy[d];
                if (X < 0 || Y < 0 || X >= N || Y >= N || chk[X][Y]) continue;
                if (map[X][Y] < L || map[X][Y] > R) continue;
                chk[X][Y] = true;
                queue.add(new Point(X, Y));
            }
        }
        return false;
    }

    public static void solve() {
        int L = minVal;
        int R = minVal;

        //투 포인터 사용
        while(L <= maxVal && R <= maxVal) {
            if (bfs(L, R)) {
                int diff = R - L;
                if (result > diff) result = diff;
                L++;
            } else {
                R++;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] > maxVal) maxVal = map[i][j];
                if (map[i][j] < minVal) minVal = map[i][j];
            }
        }
        solve();
        System.out.println(result);
    }
}