백준 1981 배열에서의 이동 java

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/1981

2. 코드가 나오기까지 🛠️

1. 배열에서 나올 수 있는 숫자를 중복없이 저장 후 오름차순 정렬 (이하 list)

2. list에서 정방향 투 포인터 운용 (left 가리키는 값 = 최소값, right 가리키는 값 = 최대값)
1. left, right 가리키는 값의 차이로 (N,N)까지 도달했을 경우, left를 올려서 격차를 좁힌다. (BFS 활용)
2. 도달 못 했을 경우, right를 올려서 격차를 벌린다. (BFS 활용)

3. 2번 과정을 거치면서 나왔던 최소 차이를 저장했다가 출력 (매번 최소값이 갱신되는지 체크 해야함)

(1) 시간복잡도 분석 ⏳

• 입력: $O(N^{2})$

• 정렬: $O(N \log{N})$

• 투 포인터 운용하며, 매번 BFS: $O(K \times (N+ 2\times N(N-1)) \approx O(K \times N^{2})$
  (2차원 배열의 원소값이 N개이면, 상하좌우 움직일 수 있는 경우의 수는 2N(N-1) 이다.)

3. 코드 🌐

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

public class Main {
    static class Coor {
        int r;
        int c;

        public Coor(int r, int c){
            this.r = r;
            this.c = c;
        }    }    static int N;
    static int [][] arr;
    static int [][] dir = new int [][] {{0,1}, {0,-1}, {1,0}, {-1,0}};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int [N][N];
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                set.add(arr[i][j]);
            }        }        System.out.println(two_pointer(set));
    }
    public static int two_pointer(HashSet<Integer> set){
        int answer = Integer.MAX_VALUE;
        ArrayList<Integer> list = new ArrayList<>(set);
        list.sort(Comparator.comparingInt(a-> a));

        int left, right;
        left = right = 0;
        while (left < list.size() && right < list.size()){
            if(left > right) right++;
            boolean result = isFinish(list.get(left), list.get(right));
            if(result) {
                answer = Math.min(answer, list.get(right) - list.get(left));
                left++;  // 되면 공간을 더 줄인다.
            }
            else right++; // 안되면 공간을 더 늘인다.
        }
        return answer;
    }

    public static boolean isFinish(int min, int max){
        boolean [][] check = new boolean[N][N];
        if(arr[0][0] < min || arr[0][0] > max) return false;
        ArrayDeque<Coor> aq = new ArrayDeque<>();
        aq.add(new Coor(0,0));
        check[0][0] = true;

        while(!aq.isEmpty()){
            Coor now = aq.poll();
            for(int i = 0; i < 4; i++){
                int nr = now.r + dir[i][0];
                int nc = now.c + dir[i][1];
                if(OOB(nr,nc) || check[nr][nc]) continue;
                if(arr[nr][nc] < min || arr[nr][nc] > max) continue;
                check[nr][nc] = true;
                aq.add(new Coor(nr, nc));
            }        }        return check[N-1][N-1];
    }
    public static boolean OOB(int r, int c){
        return r < 0 || c < 0 || r >= N || c >= N;
    }
}

4. 트러블 슈팅 or 배운 점📝

• 또 맨 첫 시작점이 최대, 최소 안에 들어오는지를 확인하지 않아서 틀렸다. 이거 조심해야겠다.