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

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

---

 

구현하면 되는 문제이다.

처음에는 board가 1이 아니고 board[nx][ny]가 board[x][y]+cost 보다 클 때 update를  해줬었는데 아래 반례를 만족시키지 못한다.

board = [[0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 0, 1, 0, 0], [1, 0, 0, 0, 1], [0, 1, 1, 0, 0]]

노란칸에서 빨간색 값(2100)이 파란색(2300) 값보다 작아서 저장을 했지만 알고보니 최종칸에서는 파란색 값이 더 작은 경우가 있었다. 이를 통해 board[i][j] 칸에서 방향을 나타내는 [좌, 하, 상, 우] arr 배열을 만들어 각 칸의 좌표와 방향을 한 묶음 시켜서 저장하였다.

 

1. x, y좌표에 대응하는 [좌, 하, 상, 우] 값을 저장하는 arr 배열을 생성한다. (default = sys.maxsize)
2. queue[z좌표, y좌표, 방향]에 시작점을 넣어준다. (방향: 좌0, 하1, 상2, 우3, 처음엔 방향이 없으므로 -1)
3. arr[0][0]을 0으로 다 초기화 해준다.
4. queue를 돌면서 현재 방향과 반대방향(좌0, 우3 / 하1, 상2 -> 합 3)일 경우 돌아가는 것이므로 pass한다. 
5. direction이 -1이 아니고 직진코스가 아니라면(i!=direction) 코스비용 500원을 추가한다.
6. 저장되있는 값보다 작다면 update해준다.
7. arr[N-1][N-1] 중 최소값을 리턴한다.

 

import sys
from collections import deque
# 좌, 하, 상, 우
dx = [0, 1, -1, 0]
dy = [-1, 0, 0, 1]


def solution(board):
    N = len(board)
    arr = [[[sys.maxsize]*4 for _ in range(N)] for _ in range(N)]
    queue = deque()

    queue.append([0, 0, -1])
    arr[0][0] = [0, 0, 0, 0]

    while queue:
        x, y, direction = queue.popleft()  
        for i in range(4):
            if i + direction == 3:
                continue
            nx = x+dx[i]
            ny = y+dy[i]
            cost = 100
            if i != direction and direction != -1:
                cost += 500
            if 0 <= nx < N and 0 <= ny < N and board[nx][ny] != 1 and arr[nx][ny][i] > cost+arr[x][y][direction]:
                arr[nx][ny][i] = cost+arr[x][y][direction]
                queue.append([nx, ny, i])
                
    return min(arr[N-1][N-1])