Note
m×n 그리드에서 왼쪽 위에서 오른쪽 아래로, 오른쪽 또는 아래로만 이동할 때 가능한 서로 다른 경로의 개수를 구하는 원리입니다.
문제 상황
로봇이 m×n 그리드의 왼쪽 위 (0, 0) 에 있고, 오른쪽 아래 (m-1, n-1) 로 이동하려고 합니다.
- 이동 규칙: 한 번에 오른쪽 또는 아래로만 한 칸 이동 가능
- 목표: 서로 다른 경로의 개수 구하기
예: 3×2 그리드에서는 경로가 3가지 (Right→Down→Down, Down→Down→Right, Down→Right→Down).
왜 동적 프로그래밍인가?
중복되는 하위 문제
어떤 칸 (y, x)에 도달하는 경로 수를 구할 때:
- (y, x)로 오는 방법은 왼쪽 (y, x-1)에서 오른쪽으로 한 칸 오거나
- 위 (y-1, x)에서 아래로 한 칸 오는 두 가지뿐입니다.
따라서 (y, x)까지의 경로 수 = (y-1, x)까지의 경로 수 + (y, x-1)까지의 경로 수
→ 작은 칸들의 경로 수를 재사용하는 DP 구조입니다.
최적 부분 구조
“(y, x)까지의 경로 수”는 “(y-1, x)까지의 경로 수”와 “(y, x-1)까지의 경로 수”만 알면 구할 수 있어서, 큰 문제가 작은 문제들로 잘 나뉩니다.
상태 정의와 점화식
상태 정의
dp[y][x]: (0, 0)에서 (y, x)까지 도달하는 서로 다른 경로의 개수
초기 조건
- 첫 번째 행 (y = 0): 왼쪽에서만 올 수 있으므로 모두 1
dp[0][x] = 1(0 ≤ x < n) - 첫 번째 열 (x = 0): 위에서만 올 수 있으므로 모두 1
dp[y][0] = 1(0 ≤ y < m)
점화식
(y ≥ 1, x ≥ 1인 일반 칸):
- (y, x)로는 (y-1, x) 에서 아래로 한 칸, (y, x-1) 에서 오른쪽으로 한 칸만 올 수 있으므로
[ dp[y][x] = dp[y-1][x] + dp[y][x-1] ]
계산 순서 (Bottom-Up)
작은 인덱스부터 채워 나가면, 점화식에 필요한 dp[y-1][x], dp[y][x-1]은 이미 계산된 상태입니다.
- 첫 행·첫 열을 1로 초기화
y = 1 .. m-1,x = 1 .. n-1순서로
dp[y][x] = dp[y-1][x] + dp[y][x-1]적용- 정답:
dp[m-1][n-1]
예시 (3×2 그리드)
| (0,0) | (0,1) |
|---|---|
| 1 | 1 |
| (1,0) | (1,1) |
| 1 | 1+1=2 |
| (2,0) | (2,1) |
| 1 | 1+2=3 |
→ (2,1)까지의 경로 수 = 3.
시간·공간 복잡도
- 시간 복잡도: O(m × n) — 그리드 한 번 순회
- 공간 복잡도: O(m × n) — 2차원 DP 테이블
(공간은 “현재 행만” 쓰는 방식으로 O(n)까지 줄일 수 있습니다.)
조합론과의 관계
오른쪽으로 (n-1)번, 아래로 (m-1)번 이동해야 하므로, 총 (m+n-2)번 이동 중 아래 이동 (m-1)번이 나올 위치를 고르는 것과 같습니다.
[ \text{경로 수} = \binom{m+n-2}{m-1} = \binom{m+n-2}{n-1} ]
수학적으로는 위 조합 한 번으로 구할 수 있고, DP는 “각 칸까지의 경로 수”를 모두 채우는 방식입니다.
관련 문제
- LeetCode 62: Unique Paths - 그리드 경로 개수 (코드 구조 설명)
- 동적 프로그래밍 (Dynamic Programming)