백준 배열에서 이동(1981)

배열에서 이동

1. 힌트

1) 배열 $S$에서 $S[i][j]$의 범위가 매우 작은 것에 주목합시다.

2) $f(l,\ r)$을 최솟값이 $l$이상, 최댓값이 $r$이하가 되도록 이동 가능한지 확인하는 판정 함수로 정의합시다. $0\le S[i][j] \le 200$에 대해서 모든 순서쌍 $l,\ r$을 모두 시도할 수 있습니다.

3) $f(l,\ r)$의 단조 증가성에 주목합니다. $f(l,\ r) = true$라면 당연히 범위가 더 널널한 $f(l,\ r + 1) = true$입니다. 단조 증가하면 이분 탐색을 적용할 수 있습니다.

2. 접근

1) 단순한 방법에서 시작할 수 있을까?

DAG가 아니기 때문에 DP를 적용할 수 없습니다. 그렇다고 그래프 탐색 도중에 지금까지 만난 가장 큰 값과 가장 작은 값을 저장하면서 다니면 그래프가 너무 커지는데다가 결국 가능한 경로를 모두 시도해봐야 해서 시간 초과를 피할 수 없습니다.

이동할 수 있는 배열의 값 $S[i][j]$의 범위를 정해놓고 이동한다면 어떨까요? 이미 방문한 칸을 얼마든지 다시 방문해도 되므로 그냥 $(1,\ 1)$에서 도달 가능한 칸만 확인하고 $(N,\ N)$이 포함되는지만 확인하면 됩니다. BFS로 구현할 수 있습니다.

2) 시간 복잡도 분석

위와 같이 $f(l,\ r)$을 최솟값이 $l$이상, 최댓값이 $r$이하가 되도록 이동 가능한지 확인하는 판정 함수로 정의합시다. $0\le S[i][j] \le 200$에 대해서 모든 순서쌍 $l,\ r$을 모두 시도할 수 있습니다. 또한 함수 $f(l,\ r)$의 시간 복잡도는 BFS이므로 $O(N^2)$입니다. 합친 시간 복잡도는 $O(N^2 \times 200 \times 200)$인데 이는 1억이 넘습니다. 잘 하면 $1$초 안에도 돌 수 있겠지만 너무 애매합니다. 다른 최적화가 가능할까요?

3) $f(l,\ r)$의 단조 증가성

$f(l,\ r)$의 단조 증가성에 주목합니다. $f(l,\ r) = true$라면 당연히 범위가 더 널널한 $f(l,\ r + 1) = true$입니다. 단조 증가하면 이분 탐색을 적용할 수 있습니다.

3. 구현

public class Main {
	static int N;
	static int[][] S;
	
	static final int[] dy = { -1, 1, 0, 0 };
	static final int[] dx = { 0, 0, -1, 1 };
	
	static boolean inRange(int y, int x) { return 0 <= y && y < N && 0 <= x && x < N; }
	
	// S[0][0]에서 시작해서 S[N - 1][N - 1]까지
	// 가장 작은 값이 l, 가장 큰 값이 r이 되게 이동할 수 있는지 여부
	static boolean f(int l, int r) {
		if (S[0][0] < l || r < S[0][0]) return false;
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] { 0, 0 });
		boolean[][] booked = new boolean[N][N];
		while (!q.isEmpty()) {
			int[] here = q.poll();
			int y = here[0]; int x = here[1];
			for (int d = 0; d < 4; d++) {
				int ny = y + dy[d]; int nx = x + dx[d];
				if (!inRange(ny, nx) || booked[ny][nx] || S[ny][nx] < l || r < S[ny][nx]) continue;
				if (ny == N - 1 && nx == N - 1) return true;
				q.offer(new int[] { ny, nx });
				booked[ny][nx] = true;
			}
		}
		return false;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		S = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) S[i][j] = Integer.parseInt(st.nextToken());
		}
		int min = 200;
		for (int l = 0; l <= 200; l++) {
			if (f(l, l)) { min = 0; break; }
			if (!f(l, 200)) continue;
			// f(l, lo) = false && f(l, hi) = true인 hi지점을 찾는다
			int lo = l; int hi = 200;
			while (lo + 1 < hi) {
				int mid = (lo + hi) / 2;
				if (f(l, mid)) hi = mid;
				else lo = mid;
			}
			min = Math.min(min, hi - l);
		}
		System.out.println(min);
	}

}

1) 시간 복잡도

판정 함수 $f(l,\ r)$은 여전히 $O(N^2)$이지만 쿼리 넣는 과정이 $200\times 200$이 아니라 $200\times lg200$이 되었습니다. 이 미묘한 최적화가 시간 초과와 맞았습니다를 나눕니다.
$O(N^2 \times 200 \times lg200)$

2) 테스트 케이스

ybin108님의 반례 모음