[프로그래머스 / Python] 등굣길

문제 링크: programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

 

 

문제 설명

해당 좌표에 도달할 수 있는 경우의 수를 저장하는 dp 테이블을 만듭니다. 

이동은 오른쪽, 아래로만 가능하므로 (x, y)에 도달하는 방법은 (x - 1, y)에서 오거나 (x, y - 1)에서 오는 2가지입니다. 

문제에서는 mxn 크기의 배열이라고 했지만 리스트 인덱싱의 편의상 n을 행, m을 열로 생각했습니다. 

 

1. (n + 1) X (m + 1) 크기의 dp 테이블을 만들고 0으로 초기화
2. dp[1][1]에 1 저장 (집 좌표)
3. puddles 좌표를 dp 테이블에 -1로 저장
4. 물에 잠기지 않은 좌표에 대해
   1) 위쪽에서 오는 방법 (x - 1, y)의 가짓수와
   2) 왼쪽에서 오는 방법 (x, y - 1)의 가짓수를 더함
5. dp[n][m]을 계산할 때까지 4번 과정 반복
6. dp[n][m]을 1000000007로 나눈 나머지 반환

 

 

 

 

소스코드

def solution(m, n, puddles):
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    dp[1][1] = 1
    # 물에 잠긴 곳 표시
    for (y, x) in puddles:
        dp[x][y] = -1
    
    for x in range(1, n + 1):
        for y in range(1, m + 1):
            if dp[x][y] != -1: # 물에 잠기지 않은 곳
                # 위쪽에서 오는 방법
                if x > 1 and dp[x - 1][y] != -1: dp[x][y] += dp[x - 1][y]
                # 왼쪽에서 오는 방법
                if y > 1 and dp[x][y - 1] != -1: dp[x][y] += dp[x][y - 1]

    return dp[n][m] % 1000000007