[백준 1981번] 배열에서의 이동 (Python3)

from collections import *
dy = [1,-1,0,0]; dx = [0,0,1,-1]

def BFS():
  dq = deque([(0,0,board[0][0],board[0][0])])
  while dq:
    y,x,m,M = dq.popleft()
    if DP[y][x][m]<=M:
      continue
    for m1 in range(m,-1,-1):
      if DP[y][x][m1]<=M:
        break
      DP[y][x][m1] = M
    for i in range(4):
      y1,x1 = y+dy[i],x+dx[i]
      if N>y1>=0 and N>x1>=0:
        dq.append((y1,x1,min(m,board[y1][x1]),max(M,board[y1][x1])))

N = int(input())
board = [[*map(int,input().split())] for i in range(N)]
DP = [[[400]*201 for i in range(N)] for i in range(N)]
BFS()
print(min(DP[-1][-1][i]-i for i in range(201)))

BFS+다이나믹 프로그래밍으로 해결하였다.

풀이가 KCM Travel [백준 10217번] KCM Travel (Python3) (tistory.com) 과 거의 유사하다.

 

풀이를 설명하면,

1. DP 배열을 3차원으로 만든다. DP[y][x][m]은 y,x에서 지금까지 지나온 수들 중 최솟값이 m일 때 지금까지 지나온 수들 중 최댓값의 최솟값을 의미한다.

2. BFS를 통해 순회하며 DP를 갱신한다. 만약 y,x,m일때 최댓값이 M이면 DP[y][x][m] 뿐만 아니라 DP[y][x][m-1], DP[y][x][m-2]...DP[y][x][0] 까지 갱신할 수 있을때까지 갱신한다. (KCM Travel의 다익스트라 방식과 유사)

3. N,N에서의 최솟값을 출력한다.

 

 

내 풀이의 경우 통과를 하긴 했지만 다른 사람들 풀이에 비해 시간이 상대적으로 오래 걸렸다. 다른 사람들 풀이를 보니 이분탐색을 이용한 풀이가 많다고 하는데 이 방식도 고민해봐야겠다.

 

 

오늘의 교훈) 이분탐색을 이용해서 해결하는 방법도 모색해보자