[프로그래머스] 경주로 건설 (Level 3)

https://programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

[프로그래머스] 경주로 건설 (Level 3)

2020 카카오 인턴십

 

최소 비용문제

-직선도로를 건설하는데는 100원, 커브길을 건설하는데는 500원이 든다. 이 때, (0,0)에서 출발해서 도로를 건설하면서 (n-1,n-1)에 도착했을 때의 최소 비용을 구하는 문제.

 

-최소 비용이라는 점에서 dp로 풀게 되었는데 이전의 주행하던 방향과 현재 확인하려는 곳의 방향이 일치한다면 최소를 확인 할 cost가 100, 그렇지 않을 경우에는 (100+500) 증가하도록 함.

 

-(0,0)에서는 오른쪽으로 출발하는 경우와, 아래쪽으로 출발하는 경우가 있기 때문에 단순히 두 케이스로 나눠줌

 

<파이썬 코드>

from collections import deque
def solution(board):
    X,L,R,U,D = -1,0,1,2,3
    dxy = [[-1,0],[1,0],[0,-1],[0,1]]
    n = len(board)
    dp = [[[float('inf'),X] for _ in range(n)] for _ in range(n)]
    for case in [R,D]:
        dp[0][0] = [0,case]
        q = deque([[0,0]])
        while q:
            x,y = q.popleft()
            for way in range(4):
                dx,dy = dxy[way]
                nx,ny = x+dx,y+dy
                if 0<=nx<n and 0<=ny<n and board[ny][nx] != 1:
                    cost = dp[y][x][0]
                    cost += 100 if dp[y][x][1] == way else 600
                    if dp[ny][nx][0] >= cost:
                        dp[ny][nx] = [cost,way]
                        q.append([nx,ny])
    return dp[-1][-1][0]