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

 문제 : boj1981

---

 

필요 알고리즘 개념

• 투 포인터, 이분 탐색
  
  • 투 포인터 혹은 이분 탐색을 섞은 그래프 탐색 문제이다. 일단 태그는 이분 탐색이긴 한데, 난 투 포인터로 풀었다.
• 그래프 탐색(BFS, DFS)
  
  • 투포인터 혹은 이분 탐색으로 제한된 범위 내에서 시작점부터 끝 점까지 탐색이 가능한지 확인해야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  이하 풀이는 투 포인터를 사용한 풀이이다. 태그를 보니 대부분 이분 탐색으로 푼 것 같다. 어차피 아이디어는 동일할 것 같다.

 

  당연히 100X100 사이즈에 대해 모든 길로 가는 경우의 수를 살펴보려면 O(2^(N^2)) 수준의 어마어마한 시간이 필요하다. 그럼 다른 방법을 생각해봐야하 하는데, 이 문제의 경우 배열의 각 수의 범위가 작아서 힌트를 너무 많이줬다(어차피 0보다 크거나 같고, 2^31보다 작거나 같다고 하더라도 서로 다른 수는 최대 N^2개 였을 것이므로 문제 없었을 것 같다.).

 

  주어지는 수의 범위가 0~200이므로 반대로 범위를 제한해서 탐색이 가능한지 매번 확인해보는 아이디어를 떠올려 적용시키면 된다. 범위 제한을 위해 모든 경우를 보면 200x200 번을 봐야 하므로, 매번 탐색할 경우 시간초과가 날 것이다(C++, C로는 이렇게만 해도 입출력까지 최적화하면 통과될 것 같긴하다). 그러니 투 포인터 혹은 이분탐색으로 범위를 제한하면 된다. 이하 투 포인터를 사용한 로직이다.

 

1. 탐색 가능한 수의 범위 [s, e] 내에서만 탐색을 할 것이다. 그러므로 시작점과 끝 점은 항상 이 범위 내에 들어가야 한다. low=min(시작점, 끝점), high=max(시작점, 끝점) 이라고 할 때, s>low거나 e<high라면 무시하면 되는 범위값이다.

 

2. 초기값으로 s=0, e=0으로 잡는다. [s, e] 범위 내에서 시작점부터 끝점까지 도달이 가능할 경우 s++를 통해 범위를 좁혀서 다시 살펴보면 되고, 도달이 불가하다면 e++를 통해 범위를 늘리면 된다. s가 e보다 커지거나, e가 문제에서 제시된 최대값(200)을 넘어갈 때 까지 해보면 된다. 이 때 문제에서 입력으로 제시되지 않았던 값은 무시하면 되므로, set 등을 통해 처리하자. 

 

3. [s,e]에 대해 탐색이 가능했던 경우 중 e-s의 최소값을 출력해주면 된다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static final int NUMBER_LIMIT = 200;
    private static final int[] DR = {-1, 0, 0, 1};
    private static final int[] DC = {0, 1, -1, 0};
    private int n, low, high;
    private int[][] arr;
    HashSet<Integer> numbers;

    private boolean isPossible(int s, int e) {
        if (s > low || e < high)
            return false;

        Queue<int[]> q = new ArrayDeque<>();
        boolean[][] v = new boolean[n][n];
        q.add(new int[]{0, 0});
        v[0][0] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0];
            int c = cur[1];
            for (int i = 0; i < 4; i++) {
                int nr = r+DR[i];
                int nc = c+DC[i];
                if (nr<0||nr>=n||nc<0||nc>=n||v[nr][nc]||arr[nr][nc]<s||arr[nr][nc]>e) continue;
                v[nr][nc] = true;
                if (nr == n-1 && nc == n-1)
                    return true;
                q.add(new int[]{nr, nc});
            }
        }
        return false;
    }

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        numbers = new HashSet<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int cur = Integer.parseInt(st.nextToken());
                numbers.add(cur);
                arr[i][j] = cur;
            }
        }
        int start = arr[0][0];
        int goal = arr[n-1][n-1];
        low = start<goal?start:goal;
        high = start<goal?goal:start;

        int s = 0, e = 0;
        int ans = NUMBER_LIMIT;
        while (s <= e && e <= NUMBER_LIMIT) {
            if (isPossible(s, e)) {
                ans = Math.min(ans, e-s);
                while (!numbers.contains(++s) && s<=e);
            } else {
                while (!numbers.contains(++e) && e<=NUMBER_LIMIT);
            }
        }
        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}