경주로 건설

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

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

import queue

def solution(board):
    x, y, N = 0, 0, len(board)
    direction = [(0, 1, 'r'), (0, -1, 'l'), (1, 0, 'd'), (-1, 0, 'u')] # 방향 및 가중치
    
    def check(r, c, d, nd): # 배열 외부, 벽, 직전에 왔던 방향이 아닌지 판별
        return 0 <= r < N and 0 <= c < N and board[r][c] == 0 and (d, nd) not in [('r', 'l'), ('l', 'r'), ('d', 'u'), ('u', 'd')]
        
    que = queue.deque()
    fees = [[float('inf') for i in range(N)] for j in range(N)] # 각 포인트 도착 최소 비용
    
    # 원점에서 출발 가능 케이스 조사
    if check(x + 1, y, '0', 'd'):
        que.append(['d', x + 1, y, 100])
        fees[x + 1][y] = 100
    if check(x, y + 1, '0', 'r'):
        que.append(['r', x, y + 1, 100])
        fees[x][y + 1] = 100
    
    while que:
        now = que.popleft()
        
        for d in direction:
            nx, ny, pred, cost = now[1] + d[0], now[2] + d[1], now[0], now[3]
            if check(nx, ny, pred, d[2]): # 도로 건설 가능하면,
                ncost = cost + 100 if pred == d[2] else cost + 600 # 직진 도로 or 커브 도로
                if ncost <= fees[nx][ny]: # 해당 포인트까지의 건설 비용이 더 싸거나 같으면,
                    que.append([d[2], nx, ny, ncost]) # 더 탐색
                    fees[nx][ny] = ncost # 최소 비용 갱신
        
    return fees[N-1][N-1]

→ 완전탐색문제, 

if ncost <= fees[nx][ny] 에서 등호가 빠지면 테스트케이스를 통과하지 못함.

해당 포인트 이후 커브를 해야 하는 케이스가 직진하고 있는 케이스 보다 먼저 que에 들어 있을 수 있기 때문이다.