LeetCode

LeetCode 62 Unique Paths 풀이: 격자 경로 동적 계획법

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

격자에서 오른쪽과 아래쪽으로만 이동할 때 목적지까지 도달하는 경로의 수를 구하는 문제다. 각 칸의 결과가 위쪽과 왼쪽 칸의 결과로 만들어지는 동적 계획법과 상태 압축을 이해해야 하므로 Level 3으로 판단했다.

1. 문제 요약

m × n 격자의 왼쪽 위에서 오른쪽 아래로 이동한다. 로봇은 한 번에 오른쪽 또는 아래쪽으로만 움직일 수 있으며, 목적지까지 가는 서로 다른 경로의 개수를 반환해야 한다.

예를 들어 m = 3, n = 2라면 아래로 두 번, 오른쪽으로 한 번 이동해야 하므로 이 세 이동의 순서를 바꾸는 3가지 경로가 있다.

오른쪽 → 아래 → 아래
아래 → 오른쪽 → 아래
아래 → 아래 → 오른쪽

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

점화식 도출

어떤 칸에 도착하는 방법은 바로 위 칸에서 아래로 내려오는 경우와 바로 왼쪽 칸에서 오른쪽으로 오는 경우뿐이다. 따라서 (row, col)에 도착하는 경로 수는 다음처럼 계산할 수 있다.

dp[row][col] = dp[row - 1][col] + dp[row][col - 1]

첫 번째 행은 오른쪽으로만 이동해야 하므로 모든 칸이 1이고, 첫 번째 열도 아래로만 이동해야 하므로 모든 칸이 1이다.

왼쪽부터 갱신해야 위쪽 상태를 덮어쓰지 않는다

2차원 표에서는 현재 칸의 위와 왼쪽 값을 읽으면 된다. 한 행만 저장할 때 dp[col]을 갱신하기 직전에는 위쪽 칸의 값이고, 이미 갱신한 dp[col - 1]은 현재 행의 왼쪽 칸 값이다. 따라서 열을 왼쪽에서 오른쪽으로 순회하며 dp[col] += dp[col - 1]을 계산한다.

공식 예제의 m = 3, n = 2에서는 첫 행이 [1, 1]이다. 다음 행에서 오른쪽 칸은 1 + 1 = 2, 마지막 행에서는 2 + 1 = 3이 되어 결과가 3이다. 오른쪽에서 왼쪽으로 갱신하면 dp[col - 1]이 아직 이전 행의 값이라 현재 행에서 방금 계산한 경로를 사용하지 못한다.

3. 문제 해결 코드 (Python)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n

        for _ in range(1, m):
            for col in range(1, n):
                dp[col] += dp[col - 1]

        return dp[-1]

각 격자 칸을 한 번씩 갱신하므로 시간 복잡도는 O(mn)이다. 열 방향 경로 수만 저장하므로 공간 복잡도는 O(n)이다.

4. 오답 접근과 반례

각 칸에서 오른쪽과 아래쪽으로 재귀 분기만 수행하면 같은 칸까지 도달하는 경우를 반복해서 계산하게 된다. 격자가 커질수록 경로 수와 재귀 호출 수가 급격히 늘어나므로 메모이제이션이나 반복형 동적 계획법이 필요하다.

모든 칸의 경로 수를 단순히 더하는 방식은 경로의 끝점과 상관없는 값을 섞는다. m = 3, n = 2에서는 목적지까지의 이동 순서가 3개뿐이므로, 각 칸에 도착하는 방법을 위쪽과 왼쪽에서만 누적해야 한다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 공식 예제와 최소 격자 경계를 확인할 수 있다.

solver = Solution()
assert solver.uniquePaths(3, 7) == 28
assert solver.uniquePaths(3, 2) == 3
assert solver.uniquePaths(1, 1) == 1

5. 공식 예제와 추가 검증

LeetCode 공식 예제 2개를 Python 3.12.4에서 실행했고 기대값과 일치했다.

예제 기대 출력 확인 결과
m = 3, n = 7 28 통과
m = 3, n = 2 3 통과

추가 검증 1: 시작점만 있는 격자

입력: m = 1, n = 1
기대 출력: 1
확인 결과: 통과
검증 목적: 이동이 필요 없는 최소 격자 확인

추가 검증 2: 한 행만 있는 격자

입력: m = 1, n = 5
기대 출력: 1
확인 결과: 통과
검증 목적: 오른쪽 이동만 가능한 경계 확인

추가 검증 3: 작은 정사각형 격자

입력: m = 3, n = 3
기대 출력: 6
확인 결과: 통과
검증 목적: 행과 열 상태가 모두 갱신되는지 확인

추가 검증 4: 중간 크기 격자

입력: m = 10, n = 10
기대 출력: 48620
확인 결과: 통과
검증 목적: 1차원 누적 상태가 여러 행에 걸쳐 유지되는지 확인

6. 참고 풀이 비교

  • Unique Paths 공식 문제는 오른쪽과 아래쪽 이동만 허용되는 격자와 입력 제한을 정의한다.
  • AlgoMonster의 설명은 각 칸의 경로 수가 위쪽과 왼쪽 경로 수의 합이라는 동적 계획법 접근을 설명한다.

2차원 DP 배열을 사용하면 상태 전이를 이해하기 쉽지만 O(mn) 공간이 필요하다. 이 글에서는 한 행을 처리할 때 필요한 정보만 남겨 1차원 배열로 압축했다. 이동 방향이 두 가지라는 조건이 바뀌면 이 압축 방식도 달라질 수 있다.

마무리

Unique Paths는 격자 문제에서 현재 위치의 결과를 이전 위치의 결과로 만드는 기본적인 동적 계획법 패턴을 보여준다. 첫 행과 첫 열의 경로 수가 1이라는 초기 상태를 만든 뒤, 왼쪽부터 값을 갱신하면 2차원 테이블 없이도 목적지의 경로 수를 계산할 수 있다.

#동적계획법#LeetCode#난이도 3