title: "[프로그래머스] 경주로 건설 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/67259"
description: "프로그래머스 Level 3 문제 [경주로 건설]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

from heapq import heappush, heappop
from math import inf

UP, RIGHT, DOWN, LEFT = 0, 1, 2, 3

# 더해지는 cost를 생각해보면,
# direction이 우측일때, 우측으로 가면 100, 아래나 위로 가면 500입니다.
# 이런 식으로 cost_dict[(DIRECTION, dr, dc)]를 만들어 둡니다.
cost_dict = {
    (RIGHT, 0, 1): 100, (RIGHT, 1, 0): 600, (RIGHT, -1, 0): 600, (RIGHT, 0, -1): inf,
    (DOWN, 1, 0): 100, (DOWN, 0, -1): 600, (DOWN, 0, 1): 600, (DOWN, -1, 0): inf,
    (UP, -1, 0): 100, (UP, 0, -1): 600, (UP, 0, 1): 600, (UP, 1, 0): inf,
    (LEFT, 0, -1): 100, (LEFT, 1, 0): 600, (LEFT, -1, 0): 600, (LEFT, 0, 1): inf,
}

drdc2direction = {
    (0, 1): RIGHT,
    (0, -1): LEFT,
    (-1, 0): UP,
    (1, 0): DOWN,
}

def solution(board):
    N = len(board)
    # 다익스트라의 변형으로 해결할 수 있습니다.
    q = []
    # 큐에는 (현재까지의 cost, r, c, 진입 방향)을 넣습니다.
    # 아래쪽과 오른쪽으로 시작할 수 있으므로 두 가지 다 넣습니다.
    heappush(q, (0, 0, 0, RIGHT))
    heappush(q, (0, 0, 0, DOWN))
    
    best_cost = {}
    best_cost[(0, 0)] = 0
    
    while q:
        cost, r, c, direction = heappop(q)
        
        # 원래 다익스트라에서는 cost > best_cost[(r, c)]이면 
        # 탐색해볼 가치가 없으므로 건너뛰었지만,
        # 지금은 도로 방향에 따라 최대 500의 비용을 아낄 가능성이 있으므로 
        # 만약 비용이 현재까지의 최소비용 + 500 이하라면 건너뛰지 않고
        # 탐색해 봅니다.
        if cost > best_cost[(r, c)] + 500:
            continue
        
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            
            # r+dr, c+dc가 board내에 있고, 벽이 아니면 다음 위치로 고려해봅니다.
            if (0 <= r+dr < N) and (0 <= c+dc < N) and board[r+dr][c+dc] != 1:
                # 현재까지의 최저 비용보다 새로운 비용이 더 작거나 같으면 업데이트하고, 
                # 다음 위치를 큐에 넣습니다.
                # 어떤 점까지 오는 비용이 같아도, 진입 방향이 다른 경우가 있을 수 있으므로
                # 현재까지의 최저비용과 같은 경우도 큐에 넣어주어야 함에 주의합니다.
                new_cost = cost + cost_dict[(direction, dr, dc)]
                if new_cost <= best_cost.get((r+dr, c+dc), inf):
                    best_cost[(r+dr, c+dc)] = new_cost
                heappush(q, (new_cost, r+dr, c+dc, drdc2direction[(dr, dc)]))
                
    return best_cost[(N-1, N-1)]

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges