[동적계획법] 프로그래머스 스쿨 - 등굣길 경로 개수 구하기와 해결 방법

웅덩이가 있는 길을 피해, 마을에서 학교까지 갈 수 있는 모든 다른 길을 찾는 문제를 해결해 보자. 이 글에서는 마을에서 학교까지 도달할 수 있는 가능한 경로의 개수를 구하는 방법과 함께, 동적 프로그래밍(DP)을 활용한 경로 추적 알고리즘을 단계별로 설명한다.

문제점: 웅덩이가 있는 경우 갈 수 있는 길이 제한된다 😓
마을에서 출발하여 학교까지 가려면 특정한 경로를 따라야 하며, 이 경로에 웅덩이가 있으면 그곳을 지날 수 없다. 따라서 웅덩이를 피해 가능한 모든 경로의 개수를 구해야 한다. 단순히 오른쪽이나 아래쪽으로만 이동할 수 있는 경우, 웅덩이를 피하면서 학교까지 도달하는 모든 가능한 경로를 찾으려면 어떻게 해야 할까?

해결책: 동적 프로그래밍을 사용한 경로 계산 🛠️
지도 그리기 먼저, 마을에서 학교까지의 길을 격자로 나타내고, 웅덩이가 있는 칸은 X로 표시한다. 마을에서 출발하여 각 칸마다 갈 수 있는 길의 개수를 표시하며, 장애물이 있는 칸은 건너뛴다.

출발점 설정 및 초기 값 지정 출발점에서 시작하여 첫 줄과 첫 세로줄을 오른쪽, 아래 방향으로 순서대로 채운다. 출발점부터 갈 수 있는 길의 개수를 1로 설정하고, 장애물이 있는 경우 해당 칸은 '0'으로 남겨둔다.

경로 개수 계산 각 칸으로 이동할 수 있는 경로의 개수를 위쪽과 왼쪽에서 오는 경로 개수의 합으로 계산한다. 장애물이 있으면 그 칸은 '0'으로 남겨둔다.

결과 확인 마지막 칸에 도달할 수 있는 경로의 개수를 구한다. 이 값이 마을에서 학교까지 도달할 수 있는 모든 가능한 경로의 수다.

예시 코드 📚
다음은 Python을 사용하여 위 과정을 구현한 코드다. 이 코드에서는 4x3 격자에서 (2, 2) 위치에 웅덩이가 있을 때의 경로 개수를 구한다.

def solution(m, n, puddles):
    dp = [[0] * m for _ in range(n)]
    
    for x, y in puddles:
        dp[y-1][x-1] = -1  # 웅덩이 표시
    
    dp[0][0] = 1  # 출발점 설정
    
    for i in range(n):
        for j in range(m):
            if dp[i][j] == -1:
                dp[i][j] = 0  # 웅덩이
                continue
            if i > 0:
                dp[i][j] += dp[i-1][j]
            if j > 0:
                dp[i][j] += dp[i][j-1]
    
    return dp[-1][-1] % 1000000007

주의할 점: 경로 계산 시 고려사항 📌
웅덩이 설정: 웅덩이는 경로 수를 0으로 설정해야 한다. 그렇지 않으면 계산 중에 잘못된 경로가 포함될 수 있다.
출발점 경로 설정: 시작 지점에서만 초기 값 1을 설정하고, 그 외 위치에서는 이전 경로를 참고해 경로 수를 채워야 한다.
모듈러 연산: 큰 수를 다루는 경우를 대비해 1,000,000,007로 모듈러 연산을 적용한다.