프로그래머스_경주로 건설

문제

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

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

풀이

직전 노드의 방향 저장

자동차의 방향이 변경되지 않으면 100원, 자동차의 방향이 변경되면 500원이 더 추가된다. 그래서 기존에 자동차가 어느 방향으로 놓여 있었는지를 확인해야 한다.

 

dp

자동차가 해당 위치에 (1) 가로방향 (2) 세로 방향으로 놓이려면, 공사비가 얼마가 드는지를 dp에 저장했다.

기존의 bfs & dfs 문제 풀이에는 해당 노드를 지난 적있는지 체크했었는데, 

여기에서는 자동차를 움직일 때 기존보다 비용이 적게 드는지 체크한다.  

heapq

기존에 더 적은 비용으로 해당 위치에 도착할 수 있다면, 탐색을 하지 않도록 했다. 그래서인지, heapq로 가장 적은 비용이 드는 것부터 꺼내 처리할 때 확실하게 적은 시간이 걸렸다.

heapq 미사용과 heapq 사용시 처리시간 비교

코드

import heapq
ALLDIR = [(0, 1), (1, 0), (0, -1), (-1, 0)] # ↓, →, ↑, ←
isConer = lambda dr, dc, xdr, xdc : abs(xdr*dr)+abs(xdc*dc)==0 # 방향이 바뀌었는지 확인
INF = 10**10 # "매우" 큰 비용

def solution(board):
    shape = (len(board), len(board[0]))
    # 각 위치에 자동차가 오려면 "매우" 큰 비용이 필요하다고 가정
    dp = [[[INF, INF] for i in range(shape[1])] for i in range(shape[0])] # ↔, ↕
    
    # (0, 0) 에 자동차가 가로로 놓여있는 경우, 
    # (0, 0) 에 자동차가 세로로 놓여있는 경우를 초기 조건으로 설정
    # 해당 위치에 자동차가 있기 위한 최소비용, 현재 위치, 자동차의 방향
    heap = [(0, 0, 0, 0, 1), (0, 0, 0, 1, 0)]  
    while heap : 
        v, r, c, xdr, xdc = heapq.heappop(heap) 
        dp[r][c][xdr] = min(dp[r][c][xdr], v)
        
        for dr, dc in ALLDIR : 
            nr, nc = r+dr, c+dc
            nv = v + (600 if isConer(dr, dc, xdr, xdc) else 100)
            
            if 0<=nr<shape[0] and 0<=nc<shape[1] : # 새로운 위치가 유효(주어진 범위 안에 있으면)
                if dp[nr][nc][dr]> nv and board[nr][nc]==0: # 자동차의 위치를 변경 시 기존보다 비용이 적게 들고 ,다음 위치가 벽이 아니라면
                    newNode = (nv, nr, nc, dr, dc)
                    heapq.heappush(heap, newNode)
                    
    return min(dp[-1][-1])