🔥

문제

윌리는 용돈이 부족해져서 삼촌을 찾아갔다. 윌리의 삼촌은 동전의 산으로 가득 찬 큰 금고를 가지고 있는데, 그 중 몇몇 동전은 매우 특별한 가치가 있는 동전이다.


하지만 최근 삼촌은 금고에 있던 코인을 옮기는 중, 우연히 아끼던 특별한 동전이 금고로 옮겨져 극도의 스트레스를 받고 있다. 다행히 그 코인을 찾았지만, 아쉽게도 금고 입구와 완전히 반대이고 금고 안에 동전이 산더미처럼 쌓여 있기 때문에 실제로 동전에 닿는 것은 쉬운 일이 아니다.


삼촌은 윌리가 동전의 산에서 특별한 동전을 회수해 올 수 있다면, 용돈을 줄 생각이 있다. 윌리는 동전을 회수하기 위한 장비로 사다리를 가져오기로 결정했지만 사다리의 길이를 얼마짜리로 준비해야 할 지 정하지 못했다. 더 긴 사다리는 더 높은 동전 절벽을 오를 수 있다는 것을 의미하지만 더 많은 비용이 든다. 따라서 윌리는 특별한 동전에 도달할 수 있는 가장 짧은 사다리를 사고 싶어한다.


금고는 왼쪽 위 모서리에 입구가 있고 특별한 동전은 오른쪽 아래 모서리에 있는 다양한 높이의 동전 더미의 직사각형 그리드로 표시될 수 있다. 윌리는 현재 서 있는 동전 더미에서 상하좌우로 인접한 동전 더미로 이동할 수 있다. 윌리는 점프하거나 날 수 없기 때문에 성공적으로 높이 x가 높은 동전더미로 이동하려면 길이 x의 사다리가 필요하다. 하지만 내려가는 것은 높이 제한 없이 중력에 모든 것을 맡길 수 있다.


윌리가 사야 할 사다리의 최단 길이를 출력해보자.

입력

첫 줄에 금고의 세로길이와 가로길이 M, N이 주어진다. (M, N은 1000 이하)
다음 M개 줄에 금고의 동전 더미의 높이가 MxN 그리드로 주어집니다. 각 동전 더미의 높이는 10억 이하의 자연수입니다.
왼쪽 위 모서리는 금고의 입구이며 오른쪽 아래는 특수 동전이다.

출력

윌리가 사야 할 사다리의 최단 길이를 출력해보자.

예제 1 입력

3 3
1 2 3
6 5 4
7 8 9

예제 1 출력

1

예제 2 입력

1 4
4 3 2 1

예제 2 출력

0

Source

from collections import deque

M, N = map(int, input().split())

_map = [0 for i in range(M)]
visited = [[0 for _ in range(N)] for _ in range(M)]

for i in range(M):
    _map[i] = list(map(int, input().split()))

l = 0
r = 1000000000

# d: 높이 차이
def bfs(d):
    q = deque()
    visited = [[0 for _ in range(N)] for _ in range(M)]
    q.append((0, 0))
    visited[0][0] = 1

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

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if(nx < 0 or nx >= M or ny < 0 or ny >= N):
                continue
            if(_map[nx][ny] - _map[x][y] > d):
                continue
            if(visited[nx][ny]):
                continue

            visited[nx][ny] = 1
            q.append((nx, ny))

    return visited[M - 1][N - 1]

while(l <= r):
    # m: 사다리의 높이
    m = (l + r) // 2

    if bfs(m):
        r = m - 1
    else:
        l = m + 1

print(l)

참고: 시간 초과(bfs 대신 다익스트라로 풀어보기)

참고