Q. 1981 자바 : 배열에서 이동

Q. 1981 자바 : 배열에서 이동

 

문제 : boj.kr/1981

P5 난이도의 문제이다.

 

문제를 간단히 설명하자면

그래프가 주어지고 1,1 ~ n,n까지 이동하려고 할 때,

거쳐간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 문제이다.

---

처음에 이분 탐색과 BFS를 활용한 방식으로 풀었고 아래와 같이 풀었지만 틀렸다.

1. 거쳐간 수들의 (최댓값-최솟값) = mid로 정의한다.

2. BFS 방식으로 이동하며 mid가 가능한지 조회한다.

3. 조건에 따라 이분탐색 방식으로 mid의 범위를 좁혀나간다

이 방법은 잘못된 방식이었다.

static boolean determination(int mid) {
    visit = new boolean[n][n];
    Queue<int[]> que = new ArrayDeque<>();
    que.add(new int[] {0, 0, map[0][0], map[0][0]});

    while (!que.isEmpty()) {
        int[] cur = que.poll();
        int curY = cur[0];
        int curX = cur[1];
        int curMin = cur[2];
        int curMax = cur[3];

        for (int i = 0; i < 4; i++) {
            int nextY = curY + dy[i];
            int nextX = curX + dx[i];

            if (nextY < 0 || nextX < 0 || nextY >= n || nextX >= n) continue;
            if (visit[nextY][nextX]) continue;

            int nextMin = Math.min(curMin, map[nextY][nextX]);
            int nextMax = Math.max(curMax, map[nextY][nextX]);
            if (nextMax - nextMin > mid) continue;

            visit[nextY][nextX] = true;
            que.add(new int[] {nextY, nextX, nextMin, nextMax});
        }
    }

    return visit[n - 1][n - 1];
}

단순 BFS 방식으로는 경로 중 최대값과 최소값을 계속 갱신해야 하는데,
동일한 위치라도 도달 경로가 다르면 값 범위가 달라질 수 있기 때문에 visit[][] 배열만으로 중복 방문을 확인하기가 어려웠다.

 

그렇다고 가능한 모든 경우의 수를 따지기 위해 DFS 방식을 사용한다면 O(2^100)으로 시간 초과가 예상되었고

아래와 같은 방식으로 풀었다.

---

위 조건에서 하나만 바꾸면 된다.

1. 거쳐간 수들 중 (최댓값-최솟값) = mid로 정의한다.

2. BFS 방식으로 이동하며 거쳐간 수가 [최소값, 최소값 + mid] 구간 내에 존재하는지 확인한다.

[최소값, 최소값 + mid] 구간 내에 거쳐간 수가 존재한다면  거쳐 간 수의(최댓값 - 최솟값) <= mid 임이 보장된다.

3. 조건에 따라 이분탐색 방식으로 mid의 범위를 좁혀나간다

 

n <= 100이고 최대 구간값 x는 200이다.

1, 3번 과정은 이분탐색으로 O(log x)

2번 과정은 구간 계산은 O(x), BFS는 O(n^2)이므로 시간복잡도는 O(x * n^2 log x)이다.

코드는 아래와 같다.

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

class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuffer sb = new StringBuffer();
    static StringTokenizer st;

    static int n;
    static int[][] map;

    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};
    static boolean[][] visit;


    static void input() throws IOException{
        n = Integer.parseInt(br.readLine());

        map = new int[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());
            }
        }
    }

    static void pro() {

        int left = 0, right = 200, result = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (determination(mid)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(result);
    }

    static boolean determination(int mid) {
        for (int min = 0; min + mid <= 200; min++) {
            int max = min + mid;
            if (map[0][0] < min || map[0][0] > max) continue;

            visit = new boolean[n][n];
            Queue<int[]> que = new ArrayDeque<>();
            que.add(new int[] {0, 0});
            visit[0][0] = true;

            while (!que.isEmpty()) {
                int[] cur = que.poll();
                int curY = cur[0];
                int curX = cur[1];

                if (curY == n - 1 && curX == n - 1) return true;

                for (int d = 0; d < 4; d++) {
                    int ny = curY + dy[d];
                    int nx = curX + dx[d];

                    if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
                    if (visit[ny][nx]) continue;
                    if (map[ny][nx] < min || map[ny][nx] > max) continue;

                    visit[ny][nx] = true;
                    que.add(new int[] {ny, nx});
                }
            }
        }

        return false;
    }

    public static void main(String[] args) throws Exception{
        input();
        pro();
    }
}