[백준] 1981번 배열에서 이동 - Python / 알고리즘 중급 1/3 - 이분 탐색 (연습)

ByungJik_Oh·2025년 7월 14일

Baekjoon Online Judge

[Baekjoon Online Judge]

목록 보기

197/244

💡 문제

n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다.

이와 같이 이동하다 보면, 배열에서 몇 개의 수를 거쳐서 이동하게 된다. 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(2 ≤ n ≤ 100)이 주어진다. 다음 n개의 줄에는 배열이 주어진다. 배열의 각 수는 0보다 크거나 같고, 200보다 작거나 같은 정수이다.

출력

첫째 줄에 (최대 - 최소)가 가장 작아질 때의 그 값을 출력한다.

💭 접근

처음 이 문제를 접했을 때는 mid를 임의의 최대값과 최솟값의 차이로 설정하고 끝까지 도달가능한 경로가 있는지 백트래킹을 사용해 모든 경로를 탐색하였지만 시간초과가 발생하였고,

두번째에는 똑같이 mid를 설정하고 BFS를 사용하여 경로를 탐색하였지만 단순한 BFS 알고리즘으로는 모든 경로를 탐색하기에는 부족하였다.

따라서 추가적인 로직이 필요헀는데, 이 문제를 해결하기 위해서 다음과 같은 순서를 따른다.

먼저 이분 탐색을 위한 변수는 다음과 같이 설정하였다.

start : 입력으로 주어질 수 있는 배열의 원소의 최소값 → 0
end : 입력으로 주어질 수 있는 배열의 원소의 최대값 → 200
mid : 임의의 경로의 최대값 - 최소값 → (start + end) // 2

이진 탐색 알고리즘으로 mid(경로 상의 최대값 - 최솟값)을 조절하며 탐색
위에서 설정한 mid가 가능한 경로를 탐색
이때 다음과 같이 mid 값을 사용하여 경로 상의 최대값과 최소값의 범위 설정 (문제 풀이의 핵심)

flag = False
for i in range(0, 201):
    min_num = i
    max_num = i + mid
    if not (min_num <= graph_start <= max_num and min_num <= graph_end <= max_num):
        continue
    if bfs(min_num, max_num):
        flag = True

위 3번에서 설정한 범위 내의 숫자로만 이루어져 있는 경로가 존재하는지 BFS로 탐색
만약 경로가 있다면 (최대 - 최소)가 더 작아질 여지가 있으므로 mid값을 줄인다.
만약 경로가 없다면 현재 mid(최대 - 최소)로는 경로를 찾을 수 없기 때문에 mid를 늘려 경로를 찾을 수 있도록 한다.

3번 로직이 핵심으로, 3번 로직 없이 단순하게 BFS로 경로를 탐색할 시 모든 경로를 고려할 수 없으므로 최적해를 찾을 수 없다.

📒 코드

import sys
from collections import deque
# input = sys.stdin.readline

def binary_search():
    start = 0
    end = 200

    ans = 0
    while start <= end:
        mid = (start + end) // 2

        flag = False
        for i in range(0, 201):
            min_num = i
            max_num = i + mid
            if not (min_num <= graph_start <= max_num and min_num <= graph_end <= max_num):
                continue
            if bfs(min_num, max_num):
                flag = True

        if flag:
            ans = mid
            end = mid - 1
        else:
            start = mid + 1
    return ans

def bfs(min_num, max_num):
    visited = [[0 for _ in range(n)] for _ in range(n)]
    visited[0][0] = 1

    q = deque()
    q.append((0, 0))
    while q:
        x, y = q.popleft()

        if x == n - 1 and y == n - 1:
            return True
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0:
                if min_num <= graph[nx][ny] <= max_num:
                    visited[nx][ny] = 1
                    q.append((nx, ny))
    return False

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
graph_start = graph[0][0]
graph_end = graph[n - 1][n - 1]

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

print(binary_search())