[프로그래머스] 경주로 건설

BFS + DP
추가 TC가 생겨서 과거 블로그의 코드가 정답이 아닌 경우가 있어 고생했다.
특히 TC25번....

from collections import deque

def solution(board):
    INF = float('inf')
    answer = INF
    N = len(board)
    visited = [[[False for _ in range(N)] for _ in range(N)] for _ in range(4)]
    total_cost = [[INF for _ in range(N)] for _ in range(N)]

    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    q = deque()
    q.append([0, 0, -1, 0]) # (x, y, direction, total_cost)
    while q:
        x, y, pre_i, cost = q.popleft()
        if (x, y) == (N - 1, N - 1):
            answer = min(answer, cost)

		# 모든 방향에 대하여 visit 처리
        for i in range(4):
            visited[i][x][y] = True
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and board[nx][ny] == 0:
            	# pre_i: 전단계의 방향, i: 나아갈 방향
                # 전단계의 방향과 나아갈 방향이 일치하는 경우, 직진
                # 전단계의 방향이 맨 처음 단계인 경우, 직진
                if pre_i == i or pre_i == -1:
                    n_cost = cost + 100
                # 다른방향인 경우 코너처리
                else:
                    n_cost = cost + 600
                    
                # 방문하지 않았으면 새로운 길 추가
                if not visited[i][nx][ny]:
                    q.append([nx, ny, i, n_cost])
                    visited[i][nx][ny] = True
                    
                # 방문했던 곳이지만, 총 비용이 더 작은 경우 업데이트
                elif n_cost <= total_cost[nx][ny]:
                    total_cost[nx][ny] = n_cost
                    q.append([nx, ny, i, n_cost])
                    
    return answer