백준 1981번 배열에서 이동

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

import collections

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def bfs(a, minimum, maximum):                       # 시작지점부터 도착지점까지의 경로값들이 최소값과 최대값내에 존재하는지 판별
    if minimum > a[0][0] or maximum < a[0][0]:
        return False
    n = len(a)
    visit = [[False] * n for _ in range(n)]
    queue = collections.deque()
    queue.append((0, 0))
    visit[0][0] = True
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if not visit[ny][nx] and minimum <= a[ny][nx] <= maximum:   # 다음 노드를 방문하지 않았고, 다음 노드 값이 최소값과 최대값사이에 있다면 이동
                    queue.append((nx, ny))
                    visit[ny][nx] = True

    return visit[-1][-1]            # 만약 도착지점을 도착하지 못했다면, False 가 반환된다.


def check(a, diff):         # 주어진 차이값을 그래프가 만족할 수 있는지 판별
    for minimum in range(200 - diff + 1):       # 최소값을 0 ~ 200-diff 까지 반복
        if bfs(a, minimum, minimum + diff):     # 최소값과 최대값을 반복하여 bfs 판별
            return True
    return False


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
left = 0
right = 200
ans = -1
while left <= right:                    # 최대값과 최소값의 차이를 이분 탐색
    mid = (left + right) // 2
    if check(a, mid):               # 해당 차이를 만족할 수 있다면, 차이를 더 줄여본다.
        right = mid - 1
        ans = mid
    else:                           # 해당 차이를 만족할 수 없다면, 차이를 더 늘린다.
        left = mid + 1

print(ans)

• 이분 탐색으로 최대값과 최소값의 차이를 찾는다.
  • 만약 주어진 차이를 만족하는 경로가 존재한다면, 차이를 더 줄인다.
    • check(a, mid) == True
  • 만약 주어진 차이를 만족하는 경로가 없다면, 차이를 더 늘린다.
    - check(a, mid) == False
    
    
• 배열의 값들은 200을 넘지 않기 때문에 check(a, diff) 에서 최소값을 0부터 200-diff 까지 반복문을 돌린다.
  • 최대값은 반복문을 돌아가고 있는 최소값에 diff 만큼 더해서 구할 수 있다.
  • bfs(a, minimum, minimum + diff)
    
    
• bfs(a, minimum, maximum) 은 bfs 를 이용해 경로를 탐색하되, 다음 경로의 값이 (배열 값) minimum 와 maximum 사이에 있어야 한다.
  • if not visit[ny][nx] and minimum <= a[ny][nx] <= maximum:

출처: 알고리즘 중급 1/3 강의
https://code.plus/course/43