프로그래머스 경주로 건설

경주로 건설

비용 구하기

경주로를 지을 다음 지점을 결정했을 때,
다음 지점과 현재 지점의 좌표를 통해 방향을 구했다.
그리고 경주로를 건설해온 방향과 같은 경우에는 100원 추가,
다르면 600원을 추가했다.
코너가 발생하면 코너뿐만 아니라 다음 경주로도 만들어지기 때문에
600원을 추가해주면 된다.

문제를 백트래킹으로 풀었기 때문에 방향을 따로 저장시켜서 변경, 복원하는 작업을 해주었다.

틀린 코드

def solution(board):
    answer = float('Inf')
    n = len(board)
    moves = [[0, 1], [1, 0], [0, -1], [-1, 0]]  # E, S, W ,N
    direction = [[1, 0], [0, 1]]
    visited = [[False for _ in range(n)] for _ in range(n)]
    visited[0][0] = True
    # Backtracking
    def get_min_cost(x, y, cost):
        nonlocal answer, visited, direction
        
        if cost >= answer:
            return
        
        if x == n - 1 and y == n - 1:
            answer = min(answer, cost)
            return

        current_direction = [dir for dir in direction]
        for dx, dy in moves:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and board[nx][ny] != 1:
                visited[nx][ny] = True
                price = 100 if [nx - x, ny - y] in direction else 600
                direction = [[nx - x, ny - y]]
                get_min_cost(nx, ny, cost + price)
                visited[nx][ny] = False
                direction = current_direction
            
    get_min_cost(0, 0, 0)
    return answer

틀린 이유

백트래킹은 완전 탐색이어서 모든 경우의 수를 찾는다.
그래서 조건을 걸어주며 최적화해야 시간 초과 없이 진행된다.

이에 대해
현재까지 만든 경로에 대한 비용이 도착지에 저장된 비용보다 크면 중단하는 조건을 걸어주었다.

그래도 시간 초과가 났는데 도착지 비용만 비교하고
중간 지점들에 대해서는 비교하지 않았기 때문이다.
중간 지점들에 대해서도 비교가 가능할텐데 그냥 DFS를 진행하니까 경우의 수가 많아져서 시간 초과가 난 것으로 추측된다.

틀린 코드에서는 방문 유무를 기준으로 백트래킹을 설계했는데
중간 지점들도 비교하기 위해서는 visited를 방문 유무가 아닌 비용을 저장하게 바꿀 필요가 있다.
그렇게 해서 DFS를 진행할지 중단할지 결정하면 된다.

코드

def solution(board):
    n = len(board)
    moves = [[0, 1], [1, 0], [0, -1], [-1, 0]]  # E, S, W ,N
    direction = [[1, 0], [0, 1]]
    visited = [[1e9 for _ in range(n)] for _ in range(n)]
    visited[0][0] = 0

    # Backtracking: 방향에 대해서만 백트래킹
    def get_min_cost(x, y):
        nonlocal visited, direction
        cost = visited[x][y]      
        current_direction = [dir for dir in direction]
        
        for dx, dy in moves:
            nx, ny = x + dx, y + dy
            price = 100 if [nx - x, ny - y] in direction else 600
						
			# 다음 위치의 비용보다 싼 경우에만 DFS 처리
            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] != 1 and visited[nx][ny] >= cost + price:
                visited[nx][ny] = cost + price
                direction = [[nx - x, ny - y]]
                get_min_cost(nx, ny)
				# DFS 이후에는 원래 방향으로 되돌아옴
                direction = current_direction
            
    get_min_cost(0, 0)
    return visited[n - 1][n - 1]

문제를 풀고나니 모든 경우의 수를 구하는 경우가 아닐 땐
BFS로 해결하는게 낫겠다고 느꼈다.
아니면 백트래킹을 무엇을 기준으로 할지 잘 생각해야겠다.