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

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

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

어려웠다...

bfs + dp로 풀어냈는데 계속 틀려서 확인해보니

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]

]

도로가 저럴 경우 꺾여서 들어오는 지점에서

[700, 100, 200, 300, 400]
[100,  X,   X,    X,   1000]
[200, 800,   X, 1700, 1100]
[X, 1400, 2000, 2300,  X]
[X  , X,    X, 2400, 3000]

1700 + 600 이면 2300이고 2000 + 100 이면 2100이라

사실은 2300 일 때가 정답인데 2100으로 처리되어서 dp가 갱신되지 않는 문제가 있다.

 

이를 코드에 추가해야 정답처리된다.

 

from collections import deque
def solution(board):
    n = len(board)
    answer = int(1e9)
    dp = [[int(1e9) for _ in range(n)] for _ in range(n)]
    directions = [(-1, 0, 0), (0, 1, 1), (1, 0, 2), (0, -1, 3)]
    q = deque([(0, 0, 0, -1)])
    while q:
        i, j, cost, dir_idx = q.popleft()
        if (i, j) == (n - 1, n - 1) and answer > cost:
            answer = cost
        for direction in directions:
            next_i = i + direction[0]
            next_j = j + direction[1]
            add_cost = 100 if dir_idx == direction[2] or dir_idx == -1 else 600
            if not (0 <= next_i < n and 0 <= next_j < n) or board[next_i][next_j] == 1:
                continue
            if dp[next_i][next_j] < cost + add_cost - 400:
                continue
            dp[next_i][next_j] = cost + add_cost
            q.append((next_i, next_j, cost + add_cost, direction[2]))
    return answer