BOJ 1981 배열에서 이동 python

최소값, 최대값의 범위 구하기.
범위마다 bfs로 도착지점까지 도달 가능한지 확인.

(최대-최소) 에 대해 이분탐색으로도 풀이가 가능하다. 최소값, 최대값의 범위를 잘못 생각해서 시간을 많이 낭비했다.

풀이 코드

import sys
from collections import deque
rl = sys.stdin.readline
n = int(rl())
g = [list(map(int, rl().split())) for _ in range(n)]
dr = [(1,0),(-1,0),(0,1),(0,-1)]
def check():
    dp = [[0 for _ in range(n)] for _ in range(n)]
    dp[0][0] = 1
    q = deque([(0,0)])
    while q:
        x, y = q.popleft()
        for dx, dy in dr:
            nx, ny = x+dx, y+dy
            if not (0<=nx<n and 0<=ny<n): continue
            if g[ny][nx] < left or g[ny][nx] > right or dp[ny][nx]: continue
            dp[ny][nx] = 1
            q.append((nx,ny))
    return dp[-1][-1]
 
ans = sys.maxsize
left, rightmax = min(map(min, g)), max(map(max, g))
leftmax = min(g[0][0], g[-1][-1])
right = max(g[0][0], g[-1][-1])
 
while left <= leftmax and right <= rightmax:
    if check():
        ans = min(ans, right-left)
        left += 1
    else: right += 1
print(ans)

문제

풀이

풀이 코드