[Baekjoon] 배열에서 이동(python)

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

문제 접근

풀이 방법이 떠오르지 않아 문제의 알고리즘 힌트와 질문 검색을 통해 문제를 해결하였다.

 

이 문제는 이분탐색 + BFS로 해결할 수 있다.

 

최댓값과 최솟값의 차이를 이분탐색을 통해 찾고 BFS를 통해 그 값이 가능한지 탐색하면 된다.

---

풀이 과정

이분 탐색을 통해 가능한 값을 찾는 것이 핵심!

while left <= right:
    mid = (left + right) // 2

    if is_available(mid):
        right = mid - 1
        answer = min(answer, mid)
    else:
        left = mid + 1

print(answer)

 

그 다음 해당 차이값으로 (0, 0)에서 (n-1, n-1)까지 탐색할 수 있는지 검사하는 함수를 작성한다.

 

이분탐색을 통해 차이값을 얻었기 때문에 범위를 지정해야 한다.

 

범위의 시작은 배열의 최솟값이고 최솟값 + 차이값이 배열의 최댓값을 넘기지 않으면 범위의 끝으로 지정할 수 있다.

def is_available(difference):
    for i in range(min_val, max_val - difference + 1):
        start, end = i, i + difference

        # 첫번째 칸이 범위를 벗어나는지 먼저 체크
        if arry[0][0] < start or arry[0][0] > end:
            continue

        if bfs(start, end):
            return True

    return False

 

마지막으로 BFS를 통해 (0, 0)에서 (n-1, n-1)까지 도달할 수 있는지 검사하면 된다.

def bfs(start, end):
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]
    visited = [[False] * n for _ in range(n)]

    q = deque()

    q.append([0, 0])
    visited[0][0] = True

    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 (
                nx < 0
                or nx >= n
                or ny < 0
                or ny >= n

                # 다음 칸이 범위에 벗어나면 탐색하지 않는다
                or arry[nx][ny] < start
                or arry[nx][ny] > end
                or visited[nx][ny]
            ):
                continue

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

    return False

---

정답 코드

"""
    백준 1981번 배열에서 이동
"""
import sys
from collections import deque


def is_available(difference):
    for i in range(min_val, max_val - difference + 1):
        start, end = i, i + difference

        # 첫번째 칸이 범위를 벗어나는지 먼저 체크
        if arry[0][0] < start or arry[0][0] > end:
            continue

        if bfs(start, end):
            return True

    return False


def bfs(start, end):
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]
    visited = [[False] * n for _ in range(n)]

    q = deque()

    q.append([0, 0])
    visited[0][0] = True

    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 (
                nx < 0
                or nx >= n
                or ny < 0
                or ny >= n

                # 다음 칸이 범위에 벗어나면 탐색하지 않는다
                or arry[nx][ny] < start
                or arry[nx][ny] > end
                or visited[nx][ny]
            ):
                continue

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

    return False


n = int(sys.stdin.readline())
arry = []
for _ in range(n):
    arry.append(list(map(int, sys.stdin.readline().split())))


min_val = sys.maxsize
max_val = -1


for i in range(n):
    for j in range(n):
        min_val = min(min_val, arry[i][j])
        max_val = max(max_val, arry[i][j])


left = 0
right = max_val - min_val
answer = max_val

while left <= right:
    mid = (left + right) // 2

    if is_available(mid):
        right = mid - 1
        answer = min(answer, mid)
    else:
        left = mid + 1

print(answer)