문제 링크

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

문제 설명

• 벽을 피해 (0, 0)에서 (n-1, n-1)로 이동하는 최소 비용 리턴
• 직선 비용 100원, 코너 비용 600원

풀이

• 백트래킹으로 모든 경로 탐색
• 최소 비용 리스트 갱신

느낀 점

• 처음 다익스트라로 시도했다가 오답 ㅠ
• 그냥 백트래킹으로만 하면 왜 안되는지 모르겠다 ㅠ
• 테케 2번이 무한루프 돔 ㅠ

코드

def solution(board):
    answer = [float('inf')]
    visited = [[False] * len(board) for _ in range(len(board))]
    visited[0][0] = True
    min_cost = [[float('inf')] * len(board) for _ in range(len(board))]
    min_cost[0][0] = 0
    dfs(board, visited, min_cost, answer, (0, 0, -1, 0))
    return answer[0]


def dfs(board, visited, min_cost, answer, curr):
    dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
    cy, cx, cd, cost = curr
    # 종료 조건
    if cy == cx == len(board) - 1:
        if answer[0] > cost:
            answer[0] = cost
            return
    # 인접 좌표 탐색
    for nd in range(4):
        ny, nx = cy + dy[nd], cx + dx[nd]
        if not (0 <= ny < len(board) and 0 <= nx < len(board)):
            continue
        if board[ny][nx] or visited[ny][nx]:
            continue
        visited[ny][nx] = True
        # 직선
        if cd < 0 or cd == nd:
            if min_cost[ny][nx] >= cost + 100:
                min_cost[ny][nx] = cost + 100
                dfs(board, visited, min_cost, answer, (ny, nx, nd, cost + 100))
        # 코너
        else:
            if min_cost[ny][nx] >= cost + 600:
                min_cost[ny][nx] = cost + 600
                dfs(board, visited, min_cost, answer, (ny, nx, nd, cost + 600))
        visited[ny][nx] = False