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

문제 링크

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

문제

n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다.

이와 같이 이동하다 보면, 배열에서 몇 개의 수를 거쳐서 이동하게 된다. 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(2 ≤ n ≤ 100)이 주어진다. 다음 n개의 줄에는 배열이 주어진다. 배열의 각 수는 0보다 크거나 같고, 200보다 작거나 같은 정수이다.

출력

첫째 줄에 (최대 - 최소)가 가장 작아질 때의 그 값을 출력한다.

알고리즘: BFS, 이분 탐색

풀이

최댓값은 전체 탐색을 하고 (0~200), 최솟값을 이분 탐색으로 찾는다.
ex)

• 최댓값이 0일 때 최솟값을 이분 탐색으로 찾고,
• 최댓값이 1일 때 최솟값을 이분 탐색으로 찾고,
• ......
• 이 작업을 최댓값이 200이 될 때까지 반복해준다.

최솟값을 이분 탐색으로 찾는 방법은 최댓값은 최솟값을 찾는 과정에서 고정값이고, BFS에 max, min 값을 전달해서 탐색에 성공하는지 실패하는지 보면 된다.
탐색에 성공했다는 의미는 최솟값을 더 올려볼 수 있다는 의미이고,
탐색에 실패했다는 의미는 최솟값을 더 내려야 한다는 의미이다.

최댓값을 고정하고 최솟값을 찾을 때 탐색이 전부 실패할 경우도 있기 때문에 꼭 탐색이 한 번이라도 성공한 경우만 따져서 그중 가장 작은 값을 출력하면 된다.

시간복잡도

• 200 log 200 n 제곱이므로 TLE 없이 통과할 수 있다.

소스 코드

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

class Node {
    int x,y;
    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static final int dx[] = {-1, 0, 1, 0};
    static final int dy[] = {0, -1, 0, 1};
    static int arr[][];
    static int N;
    static int ans = Integer.MAX_VALUE;
    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];
     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());
         }
     }
     for(int i=arr[0][0]; i<=200; i++) find_min(i);
     
     System.out.println(ans);
    }
    
    static void find_min(int max_mid) {
        int min_min = 0;
        int min_max = max_mid;
        boolean search = false;
        while(min_min <= min_max) {
            int min_mid = (min_min + min_max)/2;
            if(BFS(min_mid, max_mid)) {
                min_min = min_mid + 1;
                search = true;
            } else {
                min_max = min_mid - 1;
            }
        }
        if(search) {
            int df_v = max_mid - (min_min-1);
            if(ans > df_v) ans = df_v;
        }
    }
    
    static boolean BFS(int min, int max) {
        Queue<Node> que = new LinkedList<>();
        boolean visited[][] = new boolean[N][N];
        if(min <= arr[0][0] && arr[0][0] <= max) {
            que.add(new Node(0,0));
            visited[0][0] = true;
        }
        while(que.size() != 0) {
            Node n = que.poll();
            if((n.x == N-1) && (n.y == N-1)) return true;
            for(int i=0; i<4; i++) {
                int nx = n.x + dx[i];
                int ny = n.y + dy[i];
                if((nx>=0 && nx<=N-1) && (ny>=0 && ny<=N-1)) {
                    if(!visited[ny][nx]) {
                        if(min<= arr[ny][nx] && arr[ny][nx]<=max) {
                            que.add(new Node(nx, ny));
                            visited[ny][nx] = true;
                        }
                    }
                }
            }
        }
        return false;
    }
}