[Programmers] 경주로 건설 문제 풀이 (Python)

1. 문제 풀이

경주로를 건설하는 데 필요한 최소 비용을 계산하는 문제이다. (0,0) → (N-1,N-1)칸으로 가는 경로를 찾는 것이기때문에 BFS를 이용하면 될 것 같지만 직선 도로를 만들 때는 100원의 비용이 들고 직선도로 2개가 합쳐져 코너를 만들때는 500원의 비용이 들기 때문에 weighted graph의 최단 거리를 찾는 dijkstra를 적용하여야한다.

• 각 위치가 노드가 되고 인접해있는 칸끼리 edge가 연결되어 있다고 보면 된다.
• 각 위치마다 들어올 수 있는 방법의 수가 직선 경로 또는 코너 2가지가 존재하기 때문에 각 위치까지 가는 최소 비용을 저장하는 배열인 cost를 $N \times N$ 배열이 아닌 $N \times N \times 2$ 배열로 만들었다.
  • 가로 방향을 0, 세로 방향을 1로 설정하였다
• 나머지는 dijkstra 알고리즘을 그대로 사용하여 구현하였다.

import heapq

my = [1,-1,0,0]
mx = [0,0,1,-1]

def solution(board):
    INF,n = 1e10, len(board)
    cost,q = [[[INF] * 2 for _ in range(n)] for _ in range(n)], []
    heapq.heappush(q,(0,0,0,-1))
    while q:
        y,x,c,d = heapq.heappop(q)
        if cost[y][x][d] < c:
            continue
        for i in range(4):
            dy = y + my[i]
            dx = x + mx[i]
            if 0 <= dy < n and 0 <= dx < n and not board[dy][dx]:
                # (0,0) 위치에서 다른 위치로 가는 경로 (초기 세팅)
                # 이후 다른 노드는 모두 방향이 0 또는 1이다.
                if d == -1:
                    cost[dy][dx][abs(my[i])] = 100
                    heapq.heappush(q,(dy,dx,100,abs(my[i])))
                else:
                    temp = c+ 100 if d == abs(my[i]) else c + 100 + 500
                    if cost[dy][dx][abs(my[i])] > temp:
                        cost[dy][dx][abs(my[i])] = temp
                        heapq.heappush(q,(dy,dx,temp,abs(my[i])))
    return min(cost[n-1][n-1])