[프로그래머스] 경주로 건설 - Python

🤔 문제

---

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

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

 

😀 풀이

---

 

 본 문제는 DFS와 메모제이션 기법을 사용해서 풀이했습니다.

 

 DFS를 사용하여 만들 수 있는 모든 경로를 만들어보고 비용을 계산해봅니다. 이 과정에서 적절한 종료조건을 주어야 DFS 탐색 시간이 줄어듭니다.

 

 이를 위해 메모제이션을 사용하여 임의의 지점까지 비용이 얼마나 들었는지를 메모하고 이를 바탕으로 DFS를 적절히 종료시킵니다. 이 부분은 풀이코드 라인 12 ~ 15까지를 참고하시면 될 것 같습니다. 

 

 또한 코너 경로의 유무를 체크하기 위해 28번 라인 (dir + i) % 2 == 0 이라는 조건을 사용했습니다.

 

 이는 dx, dy 배열을 살펴보시면 무슨 의미인지 파악이 가능하실텐데 좌, 우 이동의 경우 인덱스가 0, 2에 해당합니다. 상, 하 이동의 경우는 인덱스가 1, 3에 해당하죠.

 

 따라서 (좌 or 우)에서 (상 or 하) 혹은 그 반대로 이동할 경우 dir(현재 방향), i(다음 방향)의 합이 무조건 홀수가 되게 만들었습니다.

 

 

💻 풀이 코드는 아래와 같습니다.

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
INF = 25 * 25 * 500
answer = INF

def solution(board):
    dp = [[INF] * len(board) for _ in range(len(board))]
    
    def calcCost(x, y, n, cost, dir):
        global answer
        # 지금 온 경우가 최단 비용인지 체크
        if dp[x][y] < cost:
            return
        else:
            dp[x][y] = cost
        # 종료조건
        if (x, y) == (n - 1, n - 1):
            if cost < answer:
                answer = cost
            return

        # 지나온곳 마킹
        board[x][y] = -1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if (0 <= nx < n) and (0 <= ny < n) and board[nx][ny] == 0:
                if (x, y) == (0, 0) or (dir + i) % 2 == 0:
                    calcCost(nx, ny, n, cost + 100, i)
                else:   # 코너를 만들면 500원 추가 비용
                    calcCost(nx, ny, n, cost + 600, i)
        # 마킹 해제
        board[x][y] = 0

    # 답 구하기
    calcCost(0, 0, len(board), 0, 0)
    return answer