백준 #1981 #Java

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

우선 이 문제가 이분탐색 문제인걸 인지하는 것이 먼저다.

bfs로 도착지점까지 가는 모든 경우의수를 체크하고, 경로마다 최대-최소의 값을 구하면 메모리초과가 날 것이다.
오른쪽 또는 아래로만 이동 가능하다고 하더라도 n이 100보다 작거나 같고 경우의 수만해도 대충 2^51는 되기 때문이다.

그럼 이동할 때 조건을 주며 이동을 해야될테고 경로의 최대, 최소값을 업데이트하면서 그 차이가 x이상 안나는 조건으로 이동하면 된다.
여기서 x를 선정해야되는데 이 작업을 이분탐색으로 해주면 된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int n;
	static int[][] board;
	static int[] dr = {0, 1, 0, -1};
	static int[] dc = {1, 0, -1, 0};
	public static void main(String[] args) throws Exception{
			
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());
		board = new int[n][n];

		StringTokenizer st;

		int min = 200, max = 0;

		for (int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j=0; j<n; j++) {
				int num = Integer.parseInt(st.nextToken());
				board[i][j] = num;
				min = num < min ? num : min;
				max = num > max ? num : max;
			}
		}

		int l = 0, r = max-min;
		int ans = 0;
		loop1 : while (l <= r) {
			int gap = (l + r) / 2;
			for (int i = min; i+gap <= max; i++) {
				if (hasRoute(i, i+gap)) {
					r = gap - 1;
					ans = gap;
					continue loop1;
				}
			}
			l = gap + 1;
		}
		System.out.print(ans);
	}
	static boolean hasRoute(int min, int max) {

		if (min > board[0][0] || board[0][0] > max) return false;

		boolean[][] visit = new boolean[n][n];
		Queue<int[]> que = new LinkedList<>();

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

		while (!que.isEmpty()) {
			int[] now = que.poll();
			
			if (now[0] == n-1 && now[1] == n-1) return true;

			for (int i=0; i<4; i++) {

				int nr = now[0] + dr[i], nc = now[1] + dc[i];

				if (0 <= nr && nr < n && 0 <= nc && nc < n && !visit[nr][nc]) {
					if (min <= board[nr][nc] && board[nr][nc] <= max) {
						visit[nr][nc] = true;
						que.add(new int[] {nr, nc});
					}
				}
			}
		}
		
		return false;
	}
}