경주로 건설

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)]