[프로그래머스] 경주로 건설
경주로 건설
from collections import deque
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def bfs(board, cost, direction):
n = len(board)
dist = [[1e9] * n for _ in range(n)]
dist[0][0] = 0
q = deque()
q.append([0,0, cost, direction])
while q:
x, y, c, d = q.popleft()
for dir in range(4):
nx, ny, ncost = x + dx[dir], y + dy[dir], c
while 0 <= nx < n and 0 <= ny < n:
if board[nx][ny] == 1:
break
ncost += 100 if d == dir else 600
if dist[nx][ny] > ncost:
dist[nx][ny] = ncost
q.append([nx,ny, ncost, dir])
nx += dx[dir]
ny += dy[dir]
return dist[n-1][n-1]
def solution(board):
answer = 0
return min(bfs(board, 0, 1), bfs(board, 0, 2)) # 시작 방향 : 오른쪽, 아래쪽
Author And Source
이 문제에 관하여([프로그래머스] 경주로 건설), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cheesecookie/프로그래머스-경주로-건설저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)