프로그래머스 / 경주로 건설 / python

from heapq import heappop, heappush

direction = [[1,0], [-1,0], [0,1], [0,-1]]

def solution(board):
    n= len(board)
    visited = [[0] * n for _ in range(n)]
    h = [(0, [0,0], [0,0])]
    
    while h:
        cost, now, past = heappop(h)
        x, y = now[0], now[1]
        p_x, p_y = past[0], past[1]
        
        if x == n-1 and y == n-1:
            return cost * 100
        
        visited[x][y] = cost
        
        for d in direction:
            n_x, n_y = x+d[0], y+d[1]
            if 0 <= n_x < n and 0 <= n_y < n:
                if not visited[n_x][n_y] and board[n_x][n_y] == 0:
                    if n_x != p_x and n_y != p_y:
                        heappush(h, (cost+6, [n_x,n_y], [x,y]))
                    else:
                        heappush(h, (cost+1, [n_x,n_y], [x,y]))
                        
    return answer

다익스트라 알고리즘으로 푼 문제
일반적인 bfs로 풀라면 풀 수 있겠지만 bfs로 해결 할 시 최소값을 저장하고 있을 dp가 따로 필요하다. 그렇기 때문에

다익스트라 알고리즘으로 최소 값에 대해서 우선 계산할 수 있게 끔 해준다.