Programmers. 경주로 건설

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 경주로 건설

문제 풀이

특정 지점에 도달할 때 비용이 최소로 들어야 한다는 점에서 다익스트라 알고리즘을 사용해야 한다는 점은 알아채고 적용했으나 테스트케이스 단 하나를 통과하지 못했다. 라이트업을 참고하니 특정 칸에서 어떤 경로가 더 비용이 적더라도 그 경로가 마지막 칸까지의 비용이 최소인 경로임은 보장하지 않는다는 점이다. 즉, 더 비싸더라도 다른 방향에서 접근한 경로가 마지막에서 더 저렴할 수 있다는 의미이다. 따라서, 다익스트라를 사용하되 접근할 수 있는 4개의 방향에 대한 비용을 체크하고 마지막 칸에 대해 비용 배열의 최솟값을 리턴해야 한다.

• 모든 칸에 대해 4가지 방향으로 접근한 경로의 비용을 저장할 3차원 방문 배열 정의
• 초항은 0,0에서 출발해 오른쪽과 아래쪽으로 진행이 가능하기에 board상태 체크하고 비용 업데이트 후 큐에 넣는다,
• 다익스트라를 진행하는 동안 가고자하는 노드의 현재 방향에 대한 기록된 비용보다 크다면 skip하고 그렇지 않으면 갱신한 뒤 4가지 방향에 대해 범위 체크, 방향이 다르면 커브를 의미하므로 500을 더해준다.
• 큐가 모두 비워질 때까지 탐색한 후 마지막 칸이 갖는 비용의 최솟값 리턴

python 코드

from collections import deque
def solution(board):
    N = len(board)
    INF = float('inf')
    visited = [[[INF] * 4 for _ in range(N)] for _ in range(N)]
    dr = [0, 0, 1, -1]
    dc = [1, -1, 0, 0]
    q = []
    if board[1][0] == 0:
        visited[1][0][2] = 100
        q.append((100, 1, 0, 2))
    if board[0][1] == 0:
        visited[0][1][0] = 100
        q.append((100, 0, 1, 0))
    visited[0][0] = [0,0,0,0]
    q = deque(q)
    while q:
        cost, r, c, d = q.popleft()
        if visited[r][c][d] >= cost:
            visited[r][c][d] = cost
        else:
            continue
        for i in range(4):
            nd = int(i)
            nr, nc = r + dr[nd], c + dc[nd]
            if 0 > nr or nr >= N or 0 > nc or nc >= N:
                continue
            ncost = cost + 100
            if d != nd:
                ncost += + 500
            if visited[nr][nc][nd] < ncost or board[nr][nc] == 1:
                continue
            visited[nr][nc][nd] = ncost
            q.append((ncost, nr, nc, nd))
    return min(visited[-1][-1])