[프로그래머스] 등굣길

문제

출처

이해

입력

• m, n (격자의 가로세로 크기)
  • 타입: 자연수
  • 범위: [1, 100]
• puddles (웅덩이 좌표)
  • 타입: 배열
  • 크기: [0, 10]
  • 원소:
    • 타입: 배열
    • 형태: [a, b]
    • 의미: a행 b열에는 웅덩이가 있다.

출력

• 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지

조건

1. 1행 1열에서 오른쪽 또는 아래쪽으로만 움직일 수 있다.
2. 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않는다.

예시

입력:
m: 4
n: 3
puddles: [[2, 2]]

출력:
4

접근

문제를 읽어보면 주어진 세계가 택시기하학이 적용되는 grid world임을 알 수 있다. grid world에서는 A에서 B로 가는 최단거리의 경로가 하나가 아니다. 지나온 방향으로 역행하지 않는 모든 경로가 항상 최단거리로 도달하기 때문이다. 조건 1에 의하면 역행하는 경로는 만들어지지 않는다. 그러므로 모든 경로는 최단경로이다. 따라서 1행 1열에서 m행 n열까지의 모든 경로의 수를 세면 답을 구할 수 있다.

그럼 경로의 수는 어떻게 구할 수 있을까? 다음과 같은 정의를 생각해보자.

dp[i][j]: i-1행 j-1열까지 도달하는 모든 경로의 수

조건 1에 의하면 i행 j열에 접근 가능한 위치는 i-1행 j열 또는 i행 j-1열 뿐이다. 따라서 다음과 같은 점화식을 생각할 수 있다.

\[\text{DP} [i][j] = \text{DP} [i-1][j] + \text{DP} [i][j-1]\]

단, 이 식은 항상 성립하지는 않는다. 1행이나 1열의 원소와 같은 corner case와 지날 수 없는 웅덩이를 고려해서 구현하여야 한다.

마지막으로 초기값 dp[0][0]을 결정해야 한다. 일관성을 잃지 않으면서 초기값을 결정하기 위하여 가정을 추가하자. 주어진 상황을 어딘가에서 1행 1열에 도착하는 하나의 경로가 주어졌고, 내가 그 경로를 따라와서 1행 1열에 있는 상황이라고 가정하는 것은 합리적이다. 가정에 따르면 초기값은 dp[0][0] = 1이어야함을 알 수 있다.

구현

DP

def solution(m, n, puddles):
    INF = 1000000007
    puddles = set([tuple(e - 1 for e in pos) for pos in puddles])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1
    
    for i in range(m):
        for j in range(n):
            if (i, j) in puddles: continue
            if i != 0: dp[i][j] += dp[i-1][j]
            if j != 0: dp[i][j] += dp[i][j-1]
            dp[i][j] %= INF
            
    return dp[m-1][n-1]