[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