[2020 카카오 인턴십] 경주로 건설
- 문제 푸는 시간 : 42분
- 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/67259
-
문제 정보
- 0은 비어 있음 / 1은 채워있음
- 출발 지점 : (0,0) / 도착 지점 (N-1,N-1)
- 벽이 있는 곳은 건설 할 수 없다.
- 경주로의 출발점은 (0, 0) 칸, 도착점은 (N-1, N-1) 칸
- 도착점은 (N-1, N-1) 칸을 연결하여 건설할 수 있다.
-
입력
- 도면의 상태(0은 비어 있음, 1은 벽)을 나타내는 2차원 배열 board
-
출력
- 경주로를 건설하는데 필요한 최소 비용을 return
-
코드
from collections import deque
def solution(matrix):
N, M = len(matrix), len(matrix)
dx = [0, -1, 0, 1] # 상 좌 하 우
dy = [-1, 0, 1, 0]
def iswall(nx, ny):
if nx < 0 or ny < 0:
return False
if nx >= N or ny >= M:
return False
if matrix[nx][ny] == 1:
return False
return True
def bfs(start):
queue = deque([start])
matrix[0][0]= 1
min_money = [[100000000] * N for _ in range(M)]
min_money[0][0] = 0
while queue:
x,y,cost,head = queue.popleft() # 좌표
for i in range(4): # 상 하 좌 우 좌표 살피기
nx, ny=x+dx[i], y+dy[i]
if iswall(nx,ny) :
if head != i: # 곡선 도로(모서리 + 직선)
n_cost = cost+ 600
else : # 직선 도로(직선)
n_cost = cost + 100
if n_cost < min_money[nx][ny]: # 최솟값인 경우
min_money[nx][ny] = n_cost
queue.append([nx, ny, n_cost, i])
return min_money[-1][-1]
return min(bfs((0,0,0,2)),bfs((0,0,0,3))) # 시작은 우, 하
matrix = [[0,0,0],[0,0,0],[0,0,0]]
print(solution(matrix))
Author And Source
이 문제에 관하여([2020 카카오 인턴십] 경주로 건설), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hyun0820/2020-카카오-인턴십-경주로-건설저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)