[프로그래머스 Lv.3] 경주로 건설 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/67259

프로그래머스

풀이

처음에 문제를 풀 때, 최소 거리가 최소 비용을 보장하지 않을 것으로 판단되어서 DFS로 풀이하였다. 하지만, 일부 테스트 케이스에서 시간 초과가 발생하여 다른 방법으로 풀이해야 했다. (풀이를 검색해 보니 DFS + 메모이제이션 방식으로 풀이할 수 있다고도 한다.)

###### DFS 방식으로 풀이, 시간 초과로 인해 실패 ######
def solution(board):
    dirs = [(1, 0, False), (-1, 0, False), (0, 1, True), (0, -1, True)]
    n = len(board)
    visited = [[False for _ in range(n)] for _ in range(n)]
    
    visited[0][0] = True

    min_cost = float('inf')

    def dfs(x, y, cost, is_hor):
        nonlocal min_cost
        
        if cost >= min_cost:
            return
        
        if x == n-1 and y == n-1:
            min_cost = min(min_cost, cost)
            return
        
        for dir in dirs:
            dx, dy, is_d_hor = dir
            
            nx = x + dx
            ny = y + dy
            
            if nx < 0 or nx >= n or ny < 0 or ny >= n or board[nx][ny] == 1 or visited[nx][ny]:
                continue

            visited[nx][ny] = True
            dfs(nx, ny, cost + (100 if is_hor is None or is_hor == is_d_hor else 600), is_d_hor)
            visited[nx][ny] = False
    
    dfs(0, 0, 0, None)
    return min_cost

위와 같이 기존 DFS로 구현했던 코드에서 크게 변환하지 않을 수 있는 다른 풀이 방법을 찾아보았다. 우선 순위 큐를 사용한 BFS(다익스트라)를 사용하는 방식으로 코드를 변경했다.

이 문제를 BFS를 사용해서 풀이할 수 있는 이유는 각 좌표에서 다음 좌표로 이동할 때 가중치가 다르기에 (코너와 직선 구간에서의 비용이 다르기 때문) 마치 다익스트라 문제를 푸는 것처럼 BFS + 우선순위 큐를 사용해서 풀이할 수 있는 것이다. 그리고 당연하게도 우선순위 큐를 사용해서 최솟값인 부분을 먼저 체크하기에 DFS보다 더 빠른 시간에 풀이가 가능해진다.

import heapq

# 방향이 전환된 경우인지 확인할 필요가 있으므로, 이전의 이동 방향이 가로인지 세로 방향인지를 표시해둘 필요가 있음
HOR = 1
VER = 0

def solution(board):
    n = len(board)
    dirs = [(1, 0, VER), (-1, 0, VER), (0, 1, HOR), (0, -1, HOR)] # 다음으로 (x좌표를 얼마나 이동할지 , y좌표를 얼마나 이동할지, 이동 방향이 세로인지 가로인지) 튜플들 저장

    cost = [[[float('inf')] * 2 for _ in range(n)] for _ in range(n)] # 가로 또는 세로로 이동할 때 각 좌표에서 나올 수 있는 비용의 최솟값을 저장할 배열
    
    pq = []  
    heapq.heappush(pq, (0, 0, 0, None)) # 우선순위 큐에 초기값 저장 (초기 이동 방향은 None으로 설정)

    while pq: # BFS 시작
        cur_cost, x, y, is_hor = heapq.heappop(pq) # 현재 비용이 최소인 경우부터 확인

        if x == n - 1 and y == n - 1: # 목적지에 도달했으면
            return cur_cost # 그 때의 비용이 최소 비용이 됨

        for (dx, dy, d_is_hor) in dirs: # 현재 위치에서 다음 위치로 이동할 수 있는 경우를 체크하기
            nx, ny = x + dx, y + dy # 다음 위치의 x좌표, y좌표
            
            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 0: # x좌표와 y좌표가 board 내부에 위치하고, 그 좌표에 경주로 설치가 가능하다면
            	# 만약 최초의 이동인 경우(is_hor가 None)이거나 이전 이동 방향과 동일하다면 직선 경주로만 설치하면 되기에 100만 더해주고, 이전 이동 방향과 동일하지 않다면 곡선 경주로를 설치해야하기에 500을 추가한 600을 더해줌
                new_cost = cur_cost + (100 if is_hor is None or is_hor == d_is_hor else 600) # 그 좌표에 경주로를 건설하는데 드는 비용 계산

                if new_cost < cost[nx][ny][d_is_hor]: # 만약, 현재 이동에서의 비용이 이전까지의 이동에서의 비용보다 작다면 이는 계속해서 확인할 가치가 있는 이동 경로임
                    cost[nx][ny][d_is_hor] = new_cost # 현재 좌표, 현재 이동 방향에서의 최솟값 갱신
                    heapq.heappush(pq, (new_cost, nx, ny, d_is_hor)) # 우선순위 큐에 집어넣어 이후 경로를 체크하도록 함