from collections import deque
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
dd = [0, 1, 2, 3]
INF = float('inf')
def solution(board):
answer = float('inf')
n = len(board)
dp = [[[INF for _ in range(n)] for _ in range(n)] for _ in range(4)] # 4방향에 대한 dp
q = deque([[0, 0, 0, -1]])
while q:
x, y, cost, old_direct = q.popleft()
if [x, y] == [n - 1, n - 1]:
answer = min(answer, cost)
continue
for i in range(4):
xx = x + dx[i]
yy = y + dy[i]
if 0 <= xx < n and 0 <= yy < n:
new_direct = dd[i]
new_cost = cost + 100 if old_direct == -1 or old_direct == new_direct else cost + 600
if board[xx][yy] == 0 and dp[new_direct][xx][yy] > new_cost:
dp[new_direct][xx][yy] = new_cost
q.append([xx, yy, new_cost, new_direct])
return answer
BFS , dp
왜 dp를 사용해야 할까?
일단 (x,y) 좌표까지 도달하기 위해 필요한 비용을 dp에 저장하므로써 불필요한 경우를 걸러내어 시간복잡도를 줄일 수 있다.
C 경로를 거쳐 (x, y)에 도달했던 적이 있을 때,
A, B 경로를 거쳐 (x, y)에 도달한 상황을 생각해보자.
dp[x][y] = 10 # C 경로로 x,y 에 도달할 때 소요된 비용
case 1: A 경로를 거쳐 x, y에 도달할 때 소요된 비용 == 7
case 2: B 경로를 거쳐 x, y에 도달할 때 소요된 비용 == 12
case 1의 경우 dp[x][y]
를 7로 갱신하고 stack에 담아야 한다.
case 2의 경우 stack에 담지않는다.
왜 3차원 dp일까?
(x, y)에 접근할 수 있는 방향의 수는 위, 아래, 오른쪽, 왼쪽
총 4개이고
접근하는 각 방향에 따라서 소요되는 비용이 서로 다르다.
↓ ↓
: 직선 도로를 타고 쭉 내려오는 경우 (old cost + 100)
→ ↓
: 오른쪽으로 진행하다 아래로 꺾는 경우 (old cost + 100 + 500)
↓ ←
: 왼쪽으로 진행하다가 아래로 꺾는 경우 (old cost + 100 + 500)
위와 같은 이유로 (x, y)까지 도달하기 까지 소요되는 비용을 방향마다 다르게 고려해야한다.
👉 dp[방향][x][y]