프로그래머스 - 등굣길

문제

물 웅덩이가 없는 칸만으로 학교에 갈 수 있는 경로의 수를 구하라

집은(1,1)에 학교는 (4,4)에 위치: 이 문제에서는 인덱스를 1부터 센다

입력값

• m: 가로 길이
• n: 세로 길이
• puddles: 물에 젖은 지역들 좌표

제한사항

• 1 <= m, n <= 100 (m과 n이 모두 1인 경우는 없다)
• 0 <= len(puddles) <= 10
• 학교와 집은 물에 잠기지 않는다.
• 1000000007로 나눈 나머지를 반환하라

문제풀이

1. 가장 작은 하위문제는 3가지가 있다. m과 n이 각각 2x2, 1x2, 2x1 인 경우.
2. 1x2나 2x1인 경우 각각 아래쪽이나 오른쪽에 물웅덩이가 있는가 없는가에 따라서 갈 수 있고(경로 갯수 1) 없고(경로 갯수 0)가 결정된다.
3. 2x2 의 경우 아래쪽과 오른쪽에 모두 물웅덩이가 있는 경우 갈 수 없고 (경로 갯수 0), 둘 중 한 군데에 물웅덩이가 있으면 다른 한 방향으로 갈 수 있고(경로 갯수 1), 물웅덩이가 둘 다 없으면 두 방향 모두 갈 수 있다 (경로 갯수 2).
4. 이를 확장해서 오른쪽 하단에 위치한 학교 근처 블록들부터 차근차근 계산하여 맨 왼쪽 상단에 위치한 집까지 계산해 올라오면 된다.

MAX = 1000000007

def solution(m, n, puddles):
    memo = [[1 for __ in range(m)] for _ in range(n)]
    for x, y in puddles:
        memo[y-1][x-1] = 0
    for y in reversed(range(n)):
        for x in reversed(range(m)):
            if not memo[y][x] or (x == m-1 and y == n-1):
                continue
            elif x == m - 1:
                memo[y][x] = memo[y+1][x]
            elif y == n - 1:
                memo[y][x] = memo[y][x+1]
            else:
                memo[y][x] = (memo[y+1][x] + memo[y][x+1]) % MAX
    return memo[0][0]

 

시간복잡도: O(M*N + P), M과 N은 100이하로 제한되어있고 물웅덩이도 10이하로 제한되어있으므로 O(1) 

공간복잡도: O(1)