[플래티넘 5] 백준 1981 - 배열에서 이동 (파이썬)

분류 : 이분 탐색 + BFS

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

풀이

• N x N 크기의 정수 배열 A가 주어짐
• (0, 0) → (N-1, N-1)까지 상하좌우로 이동 가능
• 단, 이동하는 칸의 숫자는 어떤 [min, max] 구간에 속해야 함
• 이때 max - min 의 최소값을 구하는 것이 목적

문제 풀이 아이디어는 다음과 같다.

• 배열의 값은 최대 200이므로 min ~ max 범위가 0~200 사이임
• max - min <= mid라고 가정하고 이동이 가능한지 BFS로 검사함
• mid 값을 이분 탐색으로 줄여나가며 최소값을 찾는 방식

초기 설정은 다음과 같이 진행한다.

low, high = 0, 200
answer = -1

mid = max_val - min_val 을 이분 탐색으로 줄여 나갈 범위이다.

이분 탐색을 시작한다.

while low <= high:
    mid = (low + high) // 2
    found = False

현재 mid를 고정하고, 어떤 min_val ~ max_val = min_val + mid 범위 내에서 시작점과 끝점을 동시에 포함하면서 도달 가능한지 확인한다.

모든 가능한 min_val을 탐색한다.

for min_val in range(200 - mid + 1):
    max_val = min_val + mid

max_val이 200을 넘지 않도록 탐색 범위를 제한한다.

시작점과 끝점이 범위에 포함되는지 확인한다.

if A[0][0] < min_val or max_val < A[0][0]:
    continue
if A[N-1][N-1] < min_val or max_val < A[N-1][N-1]:
    continue

시작점과 도착점이 범위 안에 들어있지 않으면 해당 구간은 유효하지 않다.

BFS 탐색을 시작한다.

visit = [[False]*N for _ in range(N)]
queue = deque()
queue.append((0, 0))
visit[0][0] = True

BFS로 이동 가능한지 확인하는 부분이다.

while queue:
    r, c = queue.popleft()
    for i in range(4):
        nr, nc = r + dr[i], c + dc[i]
        if nr < 0 or nr >= N or nc < 0 or nc >= N:
            continue
        if A[nr][nc] < min_val or A[nr][nc] > max_val:
            continue
        if not visit[nr][nc]:
            visit[nr][nc] = True
            queue.append((nr, nc))

min_val ~ max_val 범위 내 값만 탐색하면서 방문을 체크한다.

BFS 결과에 따른 이분 탐색을 갱신한다.

if visit[N - 1][N - 1]:
    found = True
    break

도착지까지 도달했으면 더 작은 mid도 가능할 수 있으므로 high 줄인다.

if found:
    answer = mid
    high = mid - 1
else:
    low = mid + 1

코드

# 백준 1981 - 배열에서 이동
# 분류 : 이분 탐색 + BFS

from collections import deque

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

low, high = 0, 200
answer = -1
dr = [1, -1 ,0, 0]
dc = [0, 0, 1, -1]

while low <= high :
    mid = (low + high) // 2

    found = False

    for min_val in range(200 - mid + 1) :
        max_val = min_val + mid

        if A[0][0] < min_val or max_val < A[0][0] :
            continue
        if A[N - 1][N - 1] < min_val or max_val < A[N - 1][N - 1] :
            continue

        visit = [[False] * N for _ in range(N)]
        queue = deque()

        queue.append((0, 0))
        visit[0][0] = True

        while len(queue) != 0 :
            r, c= queue.popleft()

            for i in range(4) :
                nr, nc = r + dr[i], c + dc[i]

                if nr < 0 or N <= nr or nc < 0 or N <= nc :
                    continue
                if A[nr][nc] < min_val or max_val < A[nr][nc] :
                    continue
                if not visit[nr][nc] :
                    queue.append((nr, nc))
                    visit[nr][nc] = True
        
        if visit[N - 1][N - 1] :
            found = True
            break
    
    if found :
        answer = mid
        high = mid - 1
    else :
        low = mid + 1

print(answer)