[프로그래머스/파이썬] 경주로 건설(67259) 풀이

---

• 프로그래머스 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 프로그래머스 코딩테스트 연습
• 문제 링크: 경주로 건설(67259)
• 문제풀이 코드 GitHub 링크
• 풀이 언어: Python 3

풀이

문제

빈 칸(0)과 벽(1)로 된 보드에서 좌상단에서 우하단까지 경주로를 건설할 때 최소 비용을 구하는 문제입니다.

직선은 100원, 코너는 추가 500원이 듭니다.

코드

directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def solution(board):    
    n = len(board)
    
    costs = []
    
    for i in range(1,3):
        visited = [[25*25*500] * n for _ in range(n)]
        visited[0][0] = 100
        costs.append(dfs(board, n, visited, 0, 0, directions[i], 0))

    return min(costs)

def dfs(board, n, visited, r, c, last_dir, cost):
    if r >= n-1 <= c:
##        print('=====', cost)
##        for row in visited: print(*row)
##        print('=====')
        return cost
    
    results = []
    for direction in directions:
        nr, nc = r + direction[0], c + direction[1]
        if 0 <= nr < n and 0 <= nc < n and board[nr][nc] == 0:
            next_cost = cost + 100
            if direction != last_dir: next_cost += 500
            if visited[nr][nc] > next_cost:
                visited[nr][nc] = next_cost
                results.append(dfs(board, n, visited, nr, nc, direction, next_cost))
    return min(results) if results else 25*25*500


print(solution([[0,0,0],[0,0,0],[0,0,0]]))
print(solution([[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]]))
print(solution([[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]]))
print(solution([[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[0,1,0,0,0,1],[0,0,0,0,0,0]]))

설명

두 가지 시작 방향(오른쪽, 아래)을 각각 시도한 뒤 최소값을 선택합니다.

DFS로 이동하면서:

• 같은 방향 이동: +100
• 방향 전환: +600

비용이 더 작게 도착한 경우에만 탐색을 이어가도록 visited로 가지치기합니다.

---

• 프로그래머스 문제풀이 전체 목록 보기

---