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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

 

최소 비용으로 목적지에 도달해야하므로 다익스트라로 해결했다.

 

같은 방향으로 간다면 비용은 +100

다른 방향으로 간다면 +600을 해줬다.

같던 칸으로 돌아가는 경우는 어차피 비용이 더 큰값으로 해당 칸을 접근하는 것이니 고려할 필요가 없다.

 

또한 방향이 달라지면 비용이 달라지므로 해당 칸으로 들어오는 방향을 구분해줘야한다.

 

파란 원칸(1,1)칸을 봐보자.

우선순위큐에 어떤순서로 넣느냐에 따라 (1,2)의 칸에 도달하는 최소 비용이 달라진다.

(1,1)로 갈수 있는 칸은 (0,1)과 (1,0) 두곳이다. 두곳 모두 (1,1)에 도달했을 때 비용은 700이다.

하지만 (1,2)의 칸은 (0,1)이 먼저 왔다면 1300이고 (1,0)이 먼저 왔다면 800이다.

그래서 (0,1)이 먼저 방문되어지면 답을 도출하지 못한다.

따라서 들어온 방향에 따라 구분해줘야한다.

 

그래서 cost 배열을 3차원으로 하고, x,y,방향으로 인덱스를 지정했다.

 

3차원 cost배열로 다익스트라를 수행하면 된다.

 

from heapq import heappush, heappop

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

def solution(board):
    return dijkstra(board)

def dijkstra(board):
    n = len(board)
    pq = [(0,0,0,-1)]
    cost = [[[INF]*4 for _ in range(n)] for _ in range(n)]
    
    cost[0][0] = [0,0,0,0]
    while pq:
        c,x,y,dir = heappop(pq)
        
        if dir != -1 and cost[x][y][dir] != c:
            continue
        
        if (x,y) == (n-1,n-1):
            return c
        
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            
            if point_validator(nx,ny,n,board):
                if dir == -1 or dir == d:
                    if cost[nx][ny][d] > c + 100:
                        cost[nx][ny][d] = c+100
                        heappush(pq,(c+100,nx,ny,d))
                else:
                    if cost[nx][ny][d] > c + 600:
                        cost[nx][ny][d] = c+600
                        heappush(pq,(c+600,nx,ny,d))
    
def point_validator(x,y,n,board):
    if x < 0 or y < 0 or x >= n or y >= n:
        return False
    elif board[x][y] == 1:
        return False
    return True