파이썬으로 풀어보는 고유 경로(Unique Paths) 문제 — 동적 계획법 완전 정복

문제 소개

n × m 크기의 격자(n행, m열)가 있고, 그 왼쪽 상단 모서리에 로봇이 위치해 있다고 가정해 봅시다. 로봇은 임의의 시점에서 아래쪽 또는 오른쪽으로만 이동할 수 있습니다. 로봇의 목표는 격자의 오른쪽 하단 모서리(아래 표에서 'END'로 표시된 지점)에 도달하는 것입니다. 이때 시작점에서 끝점까지 갈 수 있는 고유한 경로의 총 개수를 구하는 것이 이 문제의 핵심입니다.

예를 들어 m = 3, n = 2라면 격자는 다음과 같습니다.

이 경우 출력값은 3입니다. 즉, 시작 위치에서 끝 위치까지 도달하는 서로 다른 경로는 총 3가지입니다.

1. 오른쪽 → 오른쪽 → 아래
2. 오른쪽 → 아래 → 오른쪽
3. 아래 → 오른쪽 → 오른쪽

해결 접근 방식: 동적 계획법(Dynamic Programming)

이 문제는 동적 계획법을 활용하면 효율적으로 해결할 수 있습니다. 각 칸마다 '그 칸에 도달할 수 있는 경로의 수'를 저장하는 DP 테이블을 만들고, 아래에서 위로 거꾸로 값을 채워 나가는 것이 핵심 아이디어입니다. 구체적인 단계는 다음과 같습니다.

• row := n, col := m으로 설정하고, n × m 크기의 DP 테이블을 생성한 뒤 모든 값을 -1로 초기화합니다.
• DP[row − 2, col − 1] := 1로 설정합니다.
• i를 0부터 col까지 순회하며 마지막 행을 채웁니다: DP[n − 1, i] := 1
• i를 0부터 row까지 순회하며 마지막 열을 채웁니다: DP[i, col − 1] := 1
• i를 row − 2부터 −1까지 감소시키며, 내부 반복문으로 j를 col − 2부터 −1까지 감소시키면서 다음 점화식을 적용합니다:
  DP[i, j] := DP[i + 1, j] + DP[i, j + 1]
• 최종적으로 DP[0, 0]을 반환합니다.

마지막 행과 마지막 열은 한 번 정해진 방향으로만 직진하면 되므로 경로가 각각 1개뿐입니다. 따라서 해당 칸들을 1로 초기화한 후, 나머지 칸은 '바로 아래 칸의 경로 수 + 바로 오른쪽 칸의 경로 수'를 더한 값으로 채워 나가면 됩니다.

구현 예제

다음 파이썬 코드를 통해 실제 구현 과정을 확인해 보겠습니다.

class Solution(object):
    def uniquePaths(self, m, n):
        row = n
        column = m
        dp = [[-1 for i in range(m)] for j in range(n)]
        dp[row-2][column-1] = 1
        for i in range(column):
            dp[n-1][i] = 1
        for i in range(row):
            dp[i][column-1] = 1
        for i in range(row-2, -1, -1):
            for j in range(column-2, -1, -1):
                dp[i][j] = dp[i+1][j] + dp[i][j+1]
        return dp[0][0]

ob1 = Solution()
print(ob1.uniquePaths(10, 3))

입력

m = 10, n = 3

출력

55

복잡도 분석

이 알고리즘의 시간 복잡도는 격자의 모든 칸을 한 번씩 방문하므로 O(m × n)이며, 공간 복잡도 역시 DP 테이블을 저장해야 하므로 O(m × n)입니다. 참고로 이 문제는 조합(combination) 공식을 이용하면 O(1) 공간으로도 해결할 수 있는데, 전체 이동 횟수 중 아래로 이동하는 횟수를 선택하는 조합, 즉 C(m+n−2, n−1)이 곧 정답이 됩니다.