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에서의 최솟값을 출력한다.
내 풀이의 경우 통과를 하긴 했지만 다른 사람들 풀이에 비해 시간이 상대적으로 오래 걸렸다. 다른 사람들 풀이를 보니 이분탐색을 이용한 풀이가 많다고 하는데 이 방식도 고민해봐야겠다.
오늘의 교훈) 이분탐색을 이용해서 해결하는 방법도 모색해보자