[2020 카카오 인턴쉽] 경주로 건설
문제 링크
https://programmers.co.kr/learn/courses/30/lessons/67259
문제 설명
경로가 직선도로와 코너로 이루어질 때, (0,0)에서 (N-1, N-1)까지의 최소비용을 구하는 문제이다.
BFS 기본 풀이 방법과 동일하지만, (x,y)에서의 최소 비용만 update해서는 답이 나오지 않는다.
예제 3
예제 3번의 경우를 살펴보면, 우-좌-하-상 의 방향으로 탐색한다고 했을 때 직선도로, 코너 구분 없이 최소 비용만 update할 경우
위의 파란색 경로가 최소경로로, 2600원이 나온다.
따라서 직선도로일 때 특정 좌표로 가는 비용과, 코너일 때 특정 좌표로 가는 비용 update를 분리시켜주어야 한다.
visit 배열을 3차원으로 만들어 해결할 수 있었다.
문제 코드
from collections import deque
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
INF = 25*25*25*500
def BFS(board):
queue = deque()
visit = [[[INF for _ in range(len(board[0]))] for _ in range(len(board[0]))] for _ in range(2)]
min_price = INF
x, y, prev, price = 0, 0, '', 0
visit[0][x][y] = 0
visit[1][x][y] = 0
queue.append((x, y, prev, price))
while queue:
(curx, cury, prev, price) = queue.popleft()
if curx == len(board[0])-1 and cury == len(board[0])-1:
if min_price > price:
min_price = price
for i in range(4):
nextx = curx + dx[i]
nexty = cury + dy[i]
if nextx < 0 or nextx >= len(board[0]) or nexty < 0 or nexty >= len(board[0]):
continue
if board[nextx][nexty] == 1:
continue
#현재 이동 방향 설정
if dx[i] == 0:
cur = 0
else:
cur = 1
# 직선 도로일 경우
if prev == '' or cur == prev:
add = 100
# 코너일 경우
else:
add = 100 + 500
if visit[cur][nextx][nexty] > price + add:
visit[cur][nextx][nexty] = price + add
queue.append((nextx, nexty, cur, price + add))
return min_price
def solution(board):
answer = BFS(board)
return answer
Author And Source
이 문제에 관하여([2020 카카오 인턴쉽] 경주로 건설), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sewonkim/2020-카카오-인턴쉽-경주로-건설저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)