[python] 백준 1981 배열에서 이동

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

1981번: 배열에서 이동

 

문제 해결

• (1,1)에서 (n,n)까지 가는데 거쳐간 수들 중 최솟값과 최댓값 차이를 구하는 문제
• 이동하면서 최솟값과 최댓값을 변경해가며 저장하고 갈 수도 있을 것 같은데 그러면 que안에 너무 많은 데이터가 저장이 되어 메모리 제한에 걸린다.
• 따라서 최솟값과 최댓값을 고정값으로 가져가며 그 안에 수들이 통과하여 이동할 수 있는지 확인해가는 식으로 bfs를 이용할 수 있다는 새로운 문제해결방식을 가져간다.(즉 이분탐색+BFS)
• 최솟값의 최솟값은 모든 행들(모든 열도 상관x)을 확인해가며 가장 작은 값을 찾으면 된다.
• 최솟값의 최댓값은 꼭 자니야하는 (1,1)과 (n,n)값 중 작은 값을 의미한다.
• 최댓값의 최솟값은 꼭 지나야하는 (1,1)과 (n,n)값 중 큰 값을 의미한다.
• 최댓값의 최댓값은 모든 행들을 확인해가며 가장 큰 값을 찾으면 된다.
• 그 후 최솟값을 최솟값의 최솟값에서 시작하고 최댓값을 최댓값의 최솟값에서 시작한다.
• 그렇게 (1,1)에서 (n,n)을 이동하는 bfs를 통과했을 때 answer = min(answer, right(최댓값)-left(최솟값))이 될 수 있다.
• 그러면 더 작은 값이 정답이 될 수 있는지 확인하기 위해 left += 1을 한다.
• 만약 bfs로 (1,1)에서 (n,n)을 이동하지 못한다면 최댓값 right +=1을 하여 통과할 수 있는지 확인한다.
• 만약 기존에 bfs를 한 번이상 통과하고 한 번이상 통과하지 못했다면 다음번 통과하지 못할 땐 left+=1, right+=1씩 한다. 왜냐하면 시간단축을 위해서인데 우리의 목적은 right-left의 최솟값이기 때문이다. 즉 left를 최대한 높여서 최솟값을 구해야하는데 bfs를 통과한 다음 다시 돌렸을 때 통과하지 못해 right+=1을 한다면, 다음번 돌렸을 때 bfs를 돌려서 통과를 하면 left+=1이 되는데 기존과 같은 값이 되기 때문에 의미가 없다는 것이다. (즉 left=1, right=3에서 통과해서 left=2가 되었을 때 통과를 못해서 left=2, right=4가 되었는데 이 때 통과를 해도 answer=2로 변함이 없다는 것이다. 이 경우 의미가 없다는 것이다. 우리는 answer<2인 경우가 있나 찾는 것이기 때문

 

CODE

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

def bfs():
    dxs = [1,-1,0,0]
    dys = [0,0,1,-1]

    que = deque()
    visited = [[0]*n for _ in range(n)]
    que.append((0,0))
    visited[0][0] = 1
    while que:
        x, y = que.popleft()

        if x==n-1 and y ==n-1:return 1
        for dx, dy in zip(dxs, dys):
            nx = x + dx
            ny = y + dy
            if 0<=nx<n and 0<=ny<n:
                if left <= A[nx][ny] <= right and not visited[nx][ny]:
                    visited[nx][ny] = 1
                    que.append((nx,ny))
    return 0





if __name__=='__main__':
    n = int(input())
    A = []
    # 목적지까지 되착할 수 있는 범위의 최소범위의 범위와 최대범위의 범위를 구한다.
    r_max = 0 # 가능한 최댓값의 최댓값
    l_min = sys.maxsize # 가능한 최솟값의 최솟값
    for _ in range(n):
        row = list(map(int, input().split()))
        A.append(row)
        l_min = min(l_min, min(row)) # 모든 행중의 하나는 지나가야하므로
        r_max = max(r_max, max(row)) 

    l_max = min(A[0][0], A[n-1][n-1]) # 두 점은 반드시 지나므로 지나가는 점 중 두 점 중 작은 값이 나올 수 있는 가장 큰 최솟값이다.
    r_min = max(A[0][0], A[n-1][n-1]) # 두 점은 반드시 지나므로 지나가는 점 중 두 점 중 큰 값이 나올 수 있는 가장 작은 최댓값이다.

    left, right = l_min, r_min

    answer = sys.maxsize

    while l_min<=left <= l_max and r_min<=right<=r_max:
        l_flag, r_flag = 0, 0
        if bfs():
            answer = min(answer, right-left)
            left += 1
            l_flag = 1
        else:
            if l_flag and r_flag:
                left += 1
                right +=1
            else:
                right += 1
                r_flag = 1
    print(answer)