(Python) 프로그래머스 - [카카오 인턴] 경주로 건설

in Algorithm on Programmers, Level3

[문제 링크]

풀이

from collections import deque


def solution(board):
    answer = int(1e9)
    n = len(board)
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    q = deque()
    # x,y,direction,cost
    q.append((0, 0, -1, 0))
    visited = {(0, 0, 0): 0, (0, 0, 1): 0, (0, 0, 2): 0, (0, 0, 3): 0}
    while q:
        x, y, direction, cost = q.popleft()

        for d in range(4):
            px = x + dx[d]
            py = y + dy[d]
            if 0 <= px and px < n and 0 <= py and py < n and not board[px][py]:
                if (direction - d) % 2 == 0 or direction == -1:
                    new_cost = cost + 100
                else:
                    new_cost = cost + 600

                if px == n - 1 and py == n - 1:
                    answer = min(answer, new_cost)
                elif visited.get((px, py, d)) is None or visited.get((px, py, d)) > new_cost:
                    visited[(px, py, d)] = new_cost
                    q.append((px, py, d, new_cost))

    return answer

단순하게 bfs로 풀었더니 25번 테스트 케이스에서 틀렸다. 다른 사람들 풀이로 집어넣어 보니 대부분 25번 테스트가 틀렸는데 테스트 케이스가 추가된 것 같다. bfs를 두 번 실행해서 맞는 케이스도 있는데 이건 테스트 케이스가 운이 좋게 맞아서 통과한 것 같다.
결론은 방향에 따른 비용을 모두 저장해두고 비교해야 하는 완전 탐색문제다.
그래프 이동 문제에서 쉽게 그냥 방향 이동만 하는 것이 아니라 한 번에 두칸씩 차지한다든가, 방향에 따라 다른 비용이 소요된다면 딕셔너리를 고려해야 한다.

© 2021. By Backtony