등굣길
문제
계속되는 폭우로 일부 지역이 물에 잠겼습니다.
물에 잠기지 않은 지역을 통해 집에서 학교까지 가려고 합니다.
집에서 학교까지 가는 길은 m x n 크기의 격자 모양으로 나타낼 수 있습니다.
- 집의 좌표:
(1, 1) - 학교의 좌표:
(m, n) - 이동 방향: 오른쪽, 아래쪽
격자의 크기 m, n과 물에 잠긴 지역의 좌표를 담은 2차원 배열 puddles가 주어질 때, 집에서 학교까지 갈 수 있는 최단 경로의 개수를 구해야 합니다.
경로의 개수는 1,000,000,007로 나눈 나머지를 반환합니다.
제한사항
- 격자의 크기
m,n은 1 이상 100 이하인 자연수입니다. m과n이 모두 1인 경우는 입력으로 주어지지 않습니다.- 물에 잠긴 지역은 0개 이상 10개 이하입니다.
- 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.
입출력 예
| m | n | puddles | return |
|---|---|---|---|
4 | 3 | [[2, 2]] | 4 |
사용 알고리즘
이 문제는 동적 계획법, 즉 DP를 사용해 해결할 수 있습니다.
오른쪽과 아래쪽으로만 이동할 수 있으므로, 어떤 칸에 도착하는 방법은 두 가지뿐입니다.
- 위쪽 칸에서 아래로 내려오기
- 왼쪽 칸에서 오른쪽으로 이동하기
따라서 현재 칸까지 오는 경로의 수는 다음과 같습니다.
현재 칸의 경로 수 = 위쪽 칸의 경로 수 + 왼쪽 칸의 경로 수단, 현재 칸이 물에 잠긴 지역이라면 지나갈 수 없으므로 경로의 수를 0으로 처리합니다.
풀이 과정
puddles의 좌표를 DP 배열에서 사용하기 편하도록[행, 열]형태로 바꿉니다.dp배열을(n + 1) x (m + 1)크기로 생성합니다.- 시작 위치인
dp[1][1]을1로 초기화합니다. - 격자를 왼쪽 위부터 오른쪽 아래까지 순회합니다.
- 현재 칸이 시작 위치라면 건너뜁니다.
- 현재 칸이 웅덩이라면
0으로 둡니다. - 웅덩이가 아니라면 위쪽 칸과 왼쪽 칸의 값을 더합니다.
- 최종적으로
dp[n][m]을 반환합니다.
Python 풀이
def solution(m, n, puddles):
puddles = [[q, p] for [p, q] in puddles] # 미리 puddles 좌표 거꾸로
dp = [[0] * (m + 1) for i in range(n + 1)] # dp 초기화
dp[1][1] = 1 # 집의 위치(시작위치)
for i in range(1, n + 1):
for j in range(1, m + 1):
if i == 1 and j == 1:
continue
if [i, j] in puddles: # 웅덩이 위치의 경우 값을 0으로
dp[i][j] = 0
else: # 현재 칸은 왼쪽 칸, 위 칸의 합산
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007
return dp[n][m]코드 설명
puddles = [[q, p] for [p, q] in puddles]문제에서 주어지는 웅덩이 좌표는 [x, y] 형태입니다.
하지만 DP 배열에서는 dp[행][열] 형태로 접근하므로 [y, x] 형태로 바꿔줍니다.
예를 들어 [2, 3]은 x좌표가 2, y좌표가 3이라는 뜻입니다.
DP 배열에서는 dp[3][2]로 접근해야 하므로 [3, 2]로 변환합니다.
dp = [[0] * (m + 1) for i in range(n + 1)]좌표를 1부터 사용하기 위해 배열 크기를 각각 1씩 크게 만듭니다.
dp[1][1] = 1집의 위치인 (1, 1)에서 출발하므로 시작 위치의 경로 수를 1로 설정합니다.
if [i, j] in puddles:
dp[i][j] = 0현재 칸이 웅덩이라면 지나갈 수 없습니다.
따라서 해당 칸까지 갈 수 있는 경로의 수는 0입니다.
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007현재 칸은 위쪽 칸 또는 왼쪽 칸에서 올 수 있습니다.
따라서 두 칸의 경로 수를 더해 현재 칸의 경로 수를 구합니다.
문제에서 경로 수를 1,000,000,007로 나눈 나머지를 반환하라고 했으므로, 매번 나머지 연산을 해줍니다.
시간복잡도
격자의 크기는 m x n입니다.
모든 칸을 한 번씩 확인하므로 기본 시간복잡도는 다음과 같습니다.
O(m * n)다만 위 풀이에서는 [i, j] in puddles로 웅덩이 여부를 확인합니다.
puddles의 길이를 P라고 하면, 리스트에서 포함 여부를 확인하는 데 O(P)가 걸립니다.
따라서 엄밀한 시간복잡도는 다음과 같습니다.
O(m * n * P)하지만 제한사항에서 웅덩이는 최대 10개이므로 충분히 효율적으로 동작합니다.
공간복잡도
(n + 1) x (m + 1) 크기의 DP 배열을 사용합니다.
O(m * n)핵심 정리
- 오른쪽과 아래쪽으로만 이동하므로 현재 칸은 위쪽 칸과 왼쪽 칸에서만 올 수 있다.
- 현재 칸의 경로 수는
위쪽 칸 + 왼쪽 칸이다. - 웅덩이 칸은 지나갈 수 없으므로 경로 수를
0으로 처리한다. - 문제 조건에 따라 매번
1,000,000,007로 나눈 나머지를 저장한다.
