프로그래머스 경주로 건설 with Python

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

프로그래머스

단순 그리디처럼 보였지만 알고보니까 굉장한 반례가 숨어있던(?) 문제였다...

이 반례를 찾은 사람도 정말 대단하다ㅋㅋㅋㅋ

단순히 cost가 더 적은 애로 바꿔서 계산하면 될 줄 알았는데 방향을 틀면 600원이 추가되야되기 때문에 당장은 원래 방향인 애가 더 쌌는데 다음번에는 이전 애 방향으로 내려오는 게 더 쌀 수도 있던 문제였다.

  벽    1000  벽

900     ?      벽 (옆에서 오면 1000원, 위에서 오면 1100원 -> 여기서는 옆에서 온게 더 쌈)

  벽       ?      벽 (위에서 쭉 내려오면 1200원, 꺾어서오면 1600원 -> 여기서는 위에서 온게 더 쌈)

이렇게 교차점이 생길 때 가운데서 위방향으로 내려 온 애가 가운데서는 더 비쌌는데 밑에서는 더 싼 경우가 있더라 ㄷㄷ

따라서 어떤 방향에서 왔을 때가 가장 베스트인지 방향에 따라서도 값을 비교해야하는 문제였다... (체감 레벨 4는 되는듯.....)

from collections import deque

def solution(board):
    n = len(board)
    cost = [[[1e9] * n for _ in range(n)] for _ in range(4)] # 방향, 위치에 따른 비용 리스트
    dx, dy = [0, 1, 0, -1], [1, 0, -1, 0] # 동남서북
    queue = deque([])
    
    # 4 방향의 시작점 초기화
    for i in range(4):
        cost[i][0][0] = 0
        
    # 시작점 옆 100원 초기화
    if board[0][1] == 0:
        queue.append([0, 1, 0, 100])
        cost[0][0][1] = 100
    
    # 시작점 밑 100원 초기화
    if board[1][0] == 0:
        queue.append([1, 0, 1, 100])
        cost[1][1][0] = 100
    
    while queue:
        x, y, d, c = queue.popleft() # 위치, 방향, 비용
        # 동서남북 이동
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not board[nx][ny]: # 이동 가능한 범위이며 빈칸인 경우
                new_cost = c + 100 if d == i else c + 600 # 같은 방향(ex. 오른쪽으로 가고 또 오른쪽으로 갈경우) 100 다른 방향 600
                if cost[i][nx][ny] > new_cost: # 기존 다음 위치 비용보다 더 작다면 비용 갱신
                    cost[i][nx][ny] = new_cost
                    queue.append([nx, ny, i, new_cost])  
                    
    
    # 4방향으로 온 거 다 비교해서 가장 작은 거
    return min([cost[i][-1][-1] for i in range(4)]) # 최소 비용

 

참고 : https://soohyun6879.tistory.com/258

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