[프로그래머스-파이썬] 경주로신설

https://school.programmers.co.kr/learn/courses/30/lessons/67259

 

이 문제의 핵심은 동서남북으로 탐색하며 이전 방향대비 cost가 최소화 되는 쪽으로 이동시키는 것이다.

직선으로 가면 + 100 꺾은선으로 가면 +600을 해야한다.

바로 코너비용과 한칸 이동한 비용을 합쳐야 하기 때문이다.

 

from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def solution(board):
    answer = 0
    INF = int(1e9)
    N = len(board)
    
    # 방향, x, y
    min_cost = [[[INF]*N for _ in range(N)] for _ in range(4)]
    q = deque()
    
    
    # 동,서,남,북 : 0,1,2,3
    
    if board[0][1] == 0:
        q.append((100, 0, 1, 0))
        min_cost[0][0][1] = 100

    if board[1][0] == 0:
        q.append((100, 1, 0, 2))
        min_cost[2][1][0] = 100
    
    
    while q:
        cost, x, y, direction = q.popleft()
        print(x, y)
        
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            nc = 0
            
            if 0<= nx <N and 0<=ny<N and board[nx][ny]==0:
                if i == direction:
                    nc = cost + 100
                else:
                    nc = cost + 600
                    
                if nc < min_cost[i][nx][ny]:
                    min_cost[i][nx][ny] = nc
                    q.append((nc, nx, ny, i))
    # print(min_cost)
    return min(min_cost[d][N-1][N-1] for d in range(4))