LV 3: 경주로 건설

문제 링크

LV 3: 경주로 건설

구현 방식

• 처음에 그냥 bfs로 풀으려하였으나, 최단거리만 찾아질 뿐 최소비용이 구해지지 않았다

• 이 문제는 bfs+dp 문제이다.

  • dp table을 3차원으로 선언해주었다

    • 방향마다 dp table을 나누어, [direction][x][y] 형식으로 생성해줌

  • 처음에 queue에 노드를 집어넣을 때, 오른쪽방향과 아래쪽방향으로만 이동이 가능하기 때문에, (0, 0, 0, 1)과 (0, 0, 0, 3)을 넣어주었다

  • ncost가 dp[i][nx][ny]보다 작은 경우에 dp table 값을 갱신해주고 queue에 node를 추가해주었다

• 마지막에 네 방향의 dp table의 값을 모두 비교해주어 최솟값을 찾아주었다

코드

from collections import deque

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

def solution(board):
    N = len(board)
    
    queue = deque([]); queue.append((0, 0, 0, 1)); queue.append((0, 0, 0, 3))
    dp = [[[10000]*N for n in range(N)] for d in range(4)] #방향마다 dp table을 나눔 [direction][x][y]
    
    while queue:
        x, y, cost, pre_dir = queue.popleft()

        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx < N and 0 <= ny < N and board[nx][ny] == 0:
                ncost = cost + 1
                if pre_dir != i: ncost += 5
                if ncost < dp[i][nx][ny]:
                    dp[i][nx][ny] = ncost
                    if (nx, ny) == (N-1, N-1): continue
                    queue.append((nx, ny, ncost, i))
    
    answer = 10000
    for i in range(4): answer = min(answer, dp[i][N-1][N-1])    
    return answer*100