Unique Paths
로봇은 m개의 행과 n개의 열로 이루어진 격자의 왼쪽 위 셀에서 시작하여 오른쪽 아래 셀에 도달해야 합니다. 한 번 이동할 때마다 오른쪽으로 한 셀 또는 아래쪽으로 한 셀 이동합니다. 로봇이 이동할 수 있는 서로 다른 경로의 수를 반환하세요.
함수
- minteger
- 그리드의 행 수
- ninteger
- 그리드의 열 수
- 반환값integer
- 왼쪽 위 셀에서 오른쪽 아래 셀까지의 서로 다른 경로 수
제약 조건
1 ≤ m, n ≤ 100- 정답은 최대
2 × 109이므로 부호 있는 32비트 정수에 들어갑니다.
예제
- 입력
- m = 3n = 4
- 출력
- 10
- 설명
- 모든 경로는 아래로 2번, 오른쪽으로 3번 이동하여 총 5번 이동합니다. 아래로 이동하는 5번의 이동 중 2번을 선택하면 경로가 정해지며, 선택하는 방법은 10가지입니다.
- 입력
- m = 1n = 6
- 출력
- 1
- 설명
- 행이 하나뿐이면 로봇은 오른쪽으로 5번만 이동할 수 있으므로 경로는 정확히 하나입니다.
- 입력
- m = 4n = 5
- 출력
- 35
- 설명
- 각 경로에는 아래로 3번, 오른쪽으로 4번 이동하는 동작이 있습니다. 7번의 이동 중 아래로 이동하는 3번을 고르면 7 × 6 × 5 / 6 = 35개의 경로가 나옵니다.
제출 시 숨은 테스트 +14개
후속 질문
100 × 100 격자의 답은 59자리입니다. i로 나누는 방법이 더 이상 통하지 않을 때, 공식을 사용해 어떻게 10^9+7로 나눈 나머지를 반환할 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
로봇은 한 칸으로 이동하기 직전에 어디에 있었을까요?
한 셀로 들어가는 경로는 위쪽 셀로 들어가는 경로와 왼쪽 셀로 들어가는 경로를 더한 것입니다. 맨 위 행과 맨 왼쪽 열에는 각각 경로가 정확히 하나씩 있습니다.
개수를 왼쪽에서 오른쪽으로, 행별로 채우면서 숫자 한 줄을 유지하세요. 또는 이동 순서를 직접 셀 수도 있습니다. 경로란
m+n-2개의 이동 중 아래로 가는m-1개의 이동을 선택하는 것입니다.
풀이
경로를 하나씩 나열하는 것은 답이 없습니다. 17 × 17 격자에는 이미 경로가 601,080,390개나 있습니다. 나열하지 않고 세어야 합니다. 한 칸으로 가는 경로는 위쪽 칸으로 가는 경로와 왼쪽 칸으로 가는 경로를 합한 것이므로, 격자를 한 번 훑으며 채우는 표로 바꿀 수 있습니다. 경로는 아래쪽과 오른쪽으로 이동하는 순서이기도 하며, 이를 통해 닫힌 형태의 공식을 얻을 수 있습니다.
재귀로 모든 경로 세기
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
로봇이 오른쪽 아래 칸으로 마지막 이동을 하는 상황을 생각해 보세요. 로봇은 위쪽 칸에서 아래로 이동하거나 왼쪽 칸에서 오른쪽으로 이동하며, 둘 다 이동하는 일은 없습니다. 따라서 m × n 격자를 지나는 경로는 한 행이 더 짧은 격자를 지나는 경로 uniquePaths(m-1, n)와 한 열이 더 좁은 격자를 지나는 경로 uniquePaths(m, n-1)를 더한 값입니다.
행이 하나이거나 열이 하나인 격자에 도달하면 재귀가 멈춥니다. 이때 로봇은 직선으로만 이동할 수 있으므로 경로는 정확히 1개입니다. 모든 경로는 두 이동 중 하나로 끝나므로 각 경로는 한 번씩 계산되고, 전체 합은 올바른 값입니다.
모든 경로가 1을 반환하는 기본 사례에서 끝나므로 호출 횟수가 답 자체보다 적을 수 없어 느립니다. 17 × 17 격자에서는 호출이 6억 번을 넘고, 테스트에서 답은 최대 약 1.6 × 10^9에 이릅니다. 같은 더 작은 격자를 여러 번 계산합니다. (m-1, n-1)에는 두 부모 각각에서 한 번씩 도달하며, 아래로 내려갈수록 반복 횟수가 늘어납니다.
알고리즘
m또는n이 1이면 1을 반환합니다. 경로는 직선 하나뿐입니다.- 그렇지 않으면 마지막 이동이 아래쪽인 경로의 수를 셉니다.
uniquePaths(m-1, n) - 마지막 이동이 오른쪽인 경로의 수를 셉니다.
uniquePaths(m, n-1) - 두 수의 합을 반환합니다.
def uniquePaths(m, n):
# One row or one column: the only path is a straight line
if m == 1 or n == 1:
return 1
# The last move came down from the row above or right from the column before
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)격자를 한 번에 한 행씩 채우세요
핵심 아이디어
재귀는 같은 셀을 계속해서 다시 확인하며, 셀은 m × n개뿐입니다. 필요한 셀이 항상 준비되어 있도록 순서를 정해 각 셀에 도달하는 경로 수를 한 번씩 계산하세요.
상태: paths[r][c]는 왼쪽 위 셀에서 행 r, 열 c까지 가는 경로의 수입니다. 점화식: paths[r][c] = paths[r-1][c] + paths[r][c-1]. 위쪽에서 오는 경로와 왼쪽에서 오는 경로를 더합니다. 기저 사례: 맨 위 행과 맨 왼쪽 열의 모든 셀에는 직선 경로가 하나씩 있습니다. 순서: 위쪽 셀과 왼쪽 셀을 해당 셀을 계산하기 전에 채울 수 있도록, 행별로 왼쪽에서 오른쪽으로 진행합니다.
m = 3이고 n = 4일 때 각 행은 1 1 1 1, 그다음 1 2 3 4, 마지막으로 1 3 6 10이며, 답은 마지막 셀의 값인 10입니다.
이제 채우기 과정에서 무엇을 읽는지 살펴보세요. 바로 위 행과 현재 채우는 행만 읽습니다. 그러니 행 하나만 유지하면 됩니다. row[c]를 갱신하기 전에는 여전히 위 행에서 계산된 값이 들어 있고, row[c-1]에는 왼쪽 셀의 새 값이 이미 들어 있으므로 row[c] += row[c-1]만으로 점화식을 모두 표현할 수 있습니다. 시간 복잡도는 O(m × n)으로 유지되고, 메모리 사용량은 O(m × n)에서 O(n)으로 줄어듭니다.
알고리즘
n개의 항목을 가진row를 만들고, 모든 항목을 1로 설정합니다. 이것이 맨 위 행입니다.- 맨 위 아래의 각 행에 대해 한 번씩,
m-1번 반복합니다. - 각 행에서
c가 1부터n-1까지인 동안row[c-1]을row[c]에 더합니다.row[0]은 1로 유지됩니다. 이것이 왼쪽 열입니다. row[n-1]을 반환합니다.
def uniquePaths(m, n):
# row[c] counts the paths into column c of the current row.
# The top row is all 1s: the only way along it is straight right.
row = [1] * n
for _ in range(m - 1):
for c in range(1, n):
# Paths from above (the old row[c]) plus paths from the left (the new row[c-1])
row[c] += row[c - 1]
return row[n - 1]이항 계수로 이동 횟수 세기
핵심 아이디어
모든 경로는 정확히 m-1번 아래로, n-1번 오른쪽으로 이동하며, 총 m+n-2번 이동합니다. 이동 순서는 어떤 순서든 유효한 경로입니다. 로봇은 아래로 m-1번보다 많이 이동하거나 오른쪽으로 n-1번보다 많이 이동하지 않으므로 격자 밖으로 나가지 않습니다. 따라서 경로는 m+n-2번의 이동 중 아래로 이동할 m-1번을 고르는 것과 같으며, 답은 이항 계수 C(m+n-2, m-1)입니다.
이전 접근법의 표는 옆으로 돌린 파스칼의 삼각형이므로 두 방법의 결과가 같습니다. 큰 팩토리얼을 계산하지 않고 계수를 구하려면 한 번에 인수 하나씩 계산하세요. N = m+n-2, k = min(m, n)-1로 두고, i가 1부터 k까지일 때 N-k+i를 곱한 다음 i로 나눕니다. i번째 단계가 끝나면 누적값은 C(N-k+i, i)이며 정수이므로, 나눗셈은 매번 나누어떨어집니다.
m = 3, n = 4인 경우: N = 5, k = 2이고, 값은 1 × 4 / 1 = 4, 그다음 4 × 5 / 2 = 10이 됩니다. 더 짧은 쪽을 따라 선택하면 반복 횟수를 99회 이하로 유지할 수 있습니다. 마지막 나눗셈 전의 곱은 답의 k배입니다. 17 × 17 격자의 경우 이는 16 × 601,080,390, 즉 약 9.6 × 10^9로 32비트 범위를 넘으므로 64비트 정수에 저장하세요.
알고리즘
N = m+n-2로 설정합니다. 이는 이동 횟수이며,k = min(m, n)-1입니다.- 64비트 카운트를 1로 시작합니다.
i가 1부터k까지일 때, 카운트에N-k+i를 곱한 다음i로 나눕니다.- 카운트를 반환합니다.
def uniquePaths(m, n):
# A path is m+n-2 moves; count the ways to choose which of them go down.
# Choose along the shorter side so the loop stays short.
moves = m + n - 2
k = min(m, n) - 1
count = 1
for i in range(1, k + 1):
# count goes from C(moves-k+i-1, i-1) to C(moves-k+i, i); the division is exact
count = count * (moves - k + i) // i
return count
함정과 경계 사례
경로 수를 세는 과정은 간단하므로, 버그는 격자의 가장자리와 숫자의 크기에서 숨어 있습니다.
(m+n-2)!를 계산한 뒤 나머지 두 팩토리얼로 나누면 정답보다 훨씬 먼저 오버플로가 발생합니다. 21!은 이미 64비트 범위를 벗어나며, 100 × 7 격자에서는m+n-2가 105에 이릅니다.count / i * (N-k+i)처럼 곱하기 전에 나누면count가 항상i의 배수인 것은 아니므로 소수 부분이 버려집니다. 먼저 곱하세요. 곱은 항상 정확히 나누어떨어집니다.- 정답 자체는 2^31을 넘지 않더라도
count × (N-k+i)는 2^31을 넘을 수 있습니다. 64비트 정수형에 저장하세요. - 맨 윗줄이나 맨 왼쪽 열을 1이 아닌 0으로 두면 모든 칸이 0이 됩니다. 행이 하나이거나 열이 하나인 격자에는 경로가 정확히 1개 있습니다.
C(m+n-2, m-1) = C(m+n-2, n-1)이므로 행과 열을 바꾸어도 정답은 달라지지 않습니다.
자주 묻는 질문4
고유 경로의 공식은 무엇인가요?
정답은 이항 계수 C(m+n-2, m-1)입니다. 모든 경로는 m-1번 아래로 이동하고 n-1번 오른쪽으로 이동하며, 이 이동을 일정한 순서로 수행합니다. m+n-2번의 이동 중 아래로 이동할 이동을 선택하면 경로가 정해집니다. 3 × 4 격자의 경우 C(5, 2) = 10입니다.
Unique Paths의 시간 복잡도는 얼마인가요?
동적 프로그래밍 표는 O(m × n) 시간이 걸리며, 한 행만 유지하면 O(n) 공간이 필요합니다. 이항 공식은 O(min(m, n)) 시간이 걸리고 O(1) 공간이 필요합니다. 단순 재귀는 경로 수만큼의 호출을 최소한 수행하며, 이는 m + n에 대해 지수적입니다.
일부 칸이 막혀 있을 때 고유 경로 문제를 어떻게 해결하나요?
같은 표를 사용하고, 막힌 셀의 경로 수를 0으로 설정하여 어떤 경로도 그 셀을 지나가지 않게 하세요. 맨 윗줄과 왼쪽 열은 더 이상 모두 1이 아닙니다. 맨 윗줄에서 막힌 셀 뒤에 있는 모든 셀의 경로 수는 0입니다. 모든 이동 순서가 허용된다고 가정하므로 이 공식은 더 이상 작동하지 않습니다.
왜 고유 경로 표는 파스칼의 삼각형과 일치할까요?
각 셀은 위쪽 셀과 왼쪽 셀의 값을 더합니다. 이것이 대각선을 따라 읽었을 때 파스칼의 삼각형을 만드는 규칙입니다. r행 c열의 셀에는 C(r+c, r)이 들어 있으므로, 오른쪽 아래 셀에는 C(m+n-2, m-1)이 들어 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def uniquePaths(m, n):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
m = 3 n = 4
기대값
10