문제 설명
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.
아래 그림은 m = 4, n = 3 인 경우입니다.
가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.
격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.
제한사항
격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
물에 잠긴 지역은 0개 이상 10개 이하입니다.
집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.
입출력 예
| m | n | puddles | return |
|---|---|---|---|
| 4 | 3 | [[2, 2]] | 4 |
접근
..오른쪽과 아랫쪽으로만 움직여..
라는 조건이 굉장히 함정이다.
일반적인 최단경로 문제의 경우
이동 조건은 보통 상, 하, 좌, 우 4방향이며
이런 조건에서는 보통 이미 방문한 곳을 다시 방문하는 상황이 존재하고,
이러한 불필요한 소요를 제거하기 위해 boolean 타입의 배열을 이용해서 표시하곤 한다.
또한 갈 수 없는 길들로 인해, 목적지로 도달하기 위한 경로가
미로처럼 상하좌우로 이동해야 하는 경우가 존재하여 DFS나 BFS로 풀게 된다.
하지만,
주어진 문제의 경우, 오른쪽과 아래쪽으로만 움직이기 때문에
방문한 곳을 다시 방문하는 상황은 존재하지 않고, 따라서 방문 체크를 위한 배열도 필요하지 않다.
뿐만 아니라 최단 경로를 구하기 위해 DFS나 BFS같이 트리를 탐색하는 방법을 사용할 필요가 없게되는데,
이는 이동 조건에 의해 해당 목적지에 도달 가능한 경로는 모두 최단 경로가 되기 때문이다.
따라서 아래와 같이 단순하게 2중 for문을 이용한 풀이가 가능하다.
코드
def solution(m, n, puddles):
answer = 0
dp = [[0] * (m+1) for _ in range(n+1)]
T = 1000000007
for i in range(len(puddles)): # 1
dp[puddles[i][1]][puddles[i][0]] = -1
dp[1][1] = 1 # 2
for i in range(1, n+1): # 3
for j in range(1, m+1):
if dp[i][j] == -1: continue
p_1 = dp[i-1][j] if dp[i-1][j] != -1 else 0
p_2 = dp[i][j-1] if dp[i][j-1] != -1 else 0
dp[i][j] += (p_1 % T + p_2 % T) % T
return dp[n][m]주석 1번
dp의 각 원소는 해당 좌표에서 방문 가능한 경로의 수를 저장한다.
puddles에 존재하는 방문할 수 없는 좌표를 모두 -1로 만들어준다.
이는 이후 dp를 갱신하는 과정에서 방문 가능 여부를 확인하는데 사용된다.
주석 2번
출발지 좌표인 (1, 1)의 방문 가능 경로수는 1이다.
주석 3번
2중 for문을 돌며 각 좌표에 대한 방문 가능 경로의 수를 갱신한다.
위에서 방문 불가능한 좌표의 값을 -1로 초기화 하였기 때문에
값이 -1이 아닌 경우에만 경로 수를 갱신한다.
이동은 오른쪽 또는 아래쪽으로만 가능하므로,
현재 위치의 왼쪽 또는 위쪽 좌표에 저장된 값의 합이
현재 좌표로 이동 가능한 경로의 수 이다.
다만, 왼쪽 또는 위쪽 좌표가 이동 불가능한 좌표인 경우 합산에 이용되면 안되기 때문에
조건을 따로 처리해주어야 한다.
