백준[1981] 배열에서 이동 (Python3)

완전 탐색

배열을 모두 순회하는데 O(100 * 100) 이 필요하다.
최대 - 최소의 경우, 차이가 1이라 할 때, 차이가 1이 되는 최대, 최소의 쌍은 (1, 2), (2, 3), (3, 4), ... (199, 200) 식이다.
차이가 최대 200까지 발생하니, 쌍을 구하는 것에 대한 시간 복잡도는 (199 + 198 + 197 + ... + 0) = 약 20,000 정도 된다.
총 시간 복잡도는 O(100^2) * O(199 + 198 + ... + 0) = 2억으로 시간 초과가 발생한다.

완전 탐색 최적화

배열을 일부만 탐색할 수는 없으니, 쌍을 구하는 과정에서 최적화를 수행해야 한다.
하지만, 어떤 최대, 최소의 차이 A를 구하기 위해선, 이를 만족하는 모든 경우를 확인해야만 한다.
따라서, A를 정하는 횟수를 줄여, 경우의 수를 확인하는 과정을 줄이는 방향으로 생각했다.

이분 탐색

A를 만족하는 수를 구하면, A보다 차이가 더 큰 경우에 대해서는 볼 필요가 없다.
따라서, 이분 탐색을 통해 구할 필요가 없는 범위에 대해선 건너뛰는 방향으로 정했다.
배열의 모든 수가 같은 경우, 최대 최소의 차이는 0이 되고
시작 or 도착지가 200이고, 나머지 수가 0인 경우 200이 된다.
따라서, 0 ~ 200에 대해 이분 탐색을 진행한다.

세부 구현

임의의 최대, 최소의 차이 B를 구하면, 차이가 B를 만족하는 모든 구간의 쌍에 대해 탐색을 시작한다.
예를 들자면, 차이가 2일 때, (0, 2), (1, 3), ... , (198, 200)에 대해 검사를 한다.

이 과정에서 (0, 2)에 대해 보는 경우, 지나는 경로들의 수가 0과 2 사이의 정수인지를 확인한다.
해당 쌍으로 탐색이 불가능하면, 다음 쌍을 확인한다.

B에 대한 모든 쌍을 확인했음에도, 경로를 찾지 못했다면, B의 크기를 늘린다.
반면, 하나라도 만족하는 쌍이 있는 경우, B의 범위를 줄여서 확인해 본다.

 

총 시간 복잡도는 O(100^2) * log200 * (199 + 98 + 49 + ... + 1) 정도가 되고
대략 3000만 번의 연산으로 답을 구할 수 있다.

 

코드

from collections import deque
import sys
 
input = sys.stdin.readline
N = int(input())
board = []
MIN, MAX = 256, -1
for _ in range(N):
    inputs = list(map(int, input().split()))
    for num in inputs:
        MIN = min(MIN, num)
        MAX = max(MAX, num)
    board.append(inputs)
s, e = board[0][0], board[N - 1][N - 1]
dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
 
 
def check(mid):
    condition = MAX + 1
    for i in range(MIN, condition):
        if not (i <= s <= i + mid and i <= e <= i + mid):
            continue
        if bfs(i, i + mid):
            return True
    return False
 
 
def bfs(a, b):
    visit = [[False for _ in range(N)] for _ in range(N)]
    visit[0][0] = True
    q = deque([(0, 0)])
    while q:
        hereY, hereX = q.popleft()
        if hereY == N - 1 and hereX == N - 1:
            return True
        for d in dir:
            thereY, thereX = hereY + d[0], hereX + d[1]
            if thereY < 0 or thereY >= N or thereX < 0 or thereX >= N:
                continue
            if visit[thereY][thereX]:
                continue
            num = board[thereY][thereX]
            if not (a <= num <= b):
                continue
            visit[thereY][thereX] = True
            q.append((thereY, thereX))
 
 
def main():
    left, right = 0, MAX
    ans = 0
    while left <= right:
        mid = (left + right) // 2
        if check(mid):
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    print(ans)
 
 
if __name__ == '__main__':
    main()