[프로그래머스] 경주로 건설

문제

• 경주로 부지 : N X N
  • 0: 비어있는 칸
  • 1: 벽이 있는 칸
• 출발점: (0,0) / 도착점: (N-1, N-1)
• 비용
  • 직선도로: 100원
  • 코너: 500원

도면의 상태를 나타내는 2차원 배열 board가 매개변수로 주어질 때, 경주로를 건설하는데 필요한 최소 비용을 return하도록 solution 함수를 완성해주세요.

제한사항

• board는 2차원 정사각 배열로 배열의 크기는 3 이상 25 이하입니다.
• board 배열의 각 원소의 값은 0 또는 1 입니다.
  • 도면의 가장 왼쪽 상단 좌표는 (0,0)이며, 가장 우축 하단 좌표는 (N-1, N-1)입니다.
  • 원소의 값 0은 칸이 비어 있어 도로 연결이 가능함을 1은 칸이 벽으로 채워져 있어 도로 연결이 불가능함을 나타냅니다.
• board는 항상 출발점에서 도착점까지 경주로를 건설할 수 있는 형태로 주어집니다.
• 출발점과 도착점 칸의 원소의 값은 항상 0으로 주어집니다.

풀이

너비우선탐색 + dp

• 너비우선탐색을 통해 경로탐색 합니다.
• dp 배열을 통해 해당 위치에서의 최소 비용을 저장합니다.
• 이때 주의해야 할게, 직선으로 이동하는 경우와 코너를 이동하는 경우의 가중치가 다른다는 점입니다.
  • 따라서, 각 dp에서 상하좌우 어느 방향으로 들어왔는지에 따라 다르게 저장해줘야 합니다.
  • '상하'와 '좌우'는 각 방향에 대해서 가중치가 동일하므로 하나의 데이터로 저장하였습니다.

    dp = [상하로 들어온 가중치, 좌우로 들어온 가중치]

코드

def solution(board):
    answer, m, n = 0, len(board), len(board[0])
    INF = int(1e9)
    q = list()
    dp = [[[INF,INF] for _ in range(n)] for _ in range(m)]
    
    q.append([0, 0, 0, 0])
    q.append([0, 0, 0, 1])
    dp[0][0] = [0,0]
    
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    while q:
        cost, x, y, pos = q.pop(0)
        
        for dir in range(4):
            nx, ny = x + dx[dir], y + dy[dir]
            if 0<=nx<m and 0<=ny<n and board[nx][ny] != 1:
                if pos == 0: # 위 또는 아래에서 온 경우
                    new_cost = cost + (100 if dir % 2 == 0 else 600)
                else: # 왼쪽 또는 오른쪽에서 온 경우
                    new_cost = cost + (600 if dir % 2 == 0 else 100)
                
                if dp[nx][ny][dir%2] > new_cost:
                    dp[nx][ny][dir%2] = new_cost
                    q.append([new_cost, nx, ny, dir % 2])
    
    return min(dp[m-1][n-1])