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

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

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

 

처음에는 board[][] 의 값을 비교하여 변화시켜 최솟값을 재활용하는 방법으로 구현했는데 알고 보니, 특정 위치에서 board[][] 가 최소가 아니더라도 나중에 나타나는 도로에 따라서 최종적으로 나타나는 값이 더 작을 수도 있었다.

 

그래서 dictionary 를 이용하여 해당 위치가 코너인지 직선 도로인지 판별해주는 원소를 추가하여 다익스트라 알고리즘을 구현하였다.

 

from collections import deque, defaultdict

def solution(board):
    answer = 0
    n = len(board)
    queue = deque([[0, 0, 0]])
    direction = [(-1, 0, -1), (1, 0, -1), (0, -1, 1), (0, 1, 1)]
    dic = defaultdict(int)
    
    while queue:
        x, y, d = queue.popleft()
        
        for i in direction:
            x_, y_, d_ = x + i[0], y + i[1], i[2]
            v = dic[(x, y, d)]
            
            if 0 <= x_ < n and 0 <= y_ < n and board[x_][y_] != 1:
                if d == 0:
                    v = 100
                else:
                    if d == d_:
                        v += 100
                    else:
                        v += 600
            
                if dic[(x_, y_, d_)] == 0 or dic[(x_, y_, d_)] > v:
                    dic[(x_, y_, d_)] = v
                    queue.append([x_, y_, d_])
    
    for i in [dic[(n-1, n-1, -1)], dic[(n-1, n-1, 1)]]:
        if i != 0:
            if answer == 0 or answer >= i:
                answer = i
    
    return answer