[BOJ] 1981 - 배열에서 이동 (Python)

 

 

아이디어

 

이분 탐색으로 가능한 최소 차이를 찾아 나가며, 방문할 칸의 값 범위를 제한하여 여러 경로를 방문할 수 있도록 한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

delta = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def solution():
    n = int(input())
    board = []
    numbers = set()
    for _ in range(n):
        board.append(tuple(map(int, input().split())))
        numbers.update({*board[-1]})
    numbers = sorted(numbers)
    s, e = 0, numbers[-1]-numbers[0]
    while s <= e:
        m = (s+e)//2
        for i in numbers:
            if i+m >= board[0][0] >= i:
                visited = [[0]*n for _ in range(n)]
                visited[0][0] = 1
                stack = [(0, 0)]
                while stack:
                    r, c = stack.pop()
                    for dr, dc in delta:
                        nr, nc = r+dr, c+dc
                        if n > nr >= 0 and n > nc >= 0:
                            if i+m >= board[nr][nc] >= i and visited[nr][nc] == 0:
                                visited[nr][nc] = 1
                                stack.append((nr, nc))
                if visited[-1][-1]:
                    e = m-1
                    break
        else:
            s = m+1
    print(s)

solution()