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

프로그래머스

1. 학교(m,n)에서 집(0,0)으로 가는 방법

def dfs(x, y, dp):
    if x < 0 or y < 0 or dp[y][x] == -1:
        return 0
    if dp[y][x] == 0:
        dp[y][x] = dfs(x - 1, y, dp) + dfs(x, y - 1, dp)
    return dp[y][x]


def solution(m, n, puddles):
    dp = [[0 for _ in range(m)] for _ in range(n)]
    for p in puddles:
        x, y = p
        dp[y-1][x-1] = -1
    dp[0][0] = 1
    ans = dfs(m - 1, n - 1, dp)
    return ans % 1000000007

(m,n)에서 부터 dfs를 시작해서 dp라는 배열에 현재 위치까지 오는 경우의 수를 전부 더해서 저장합니다. 

dp[0][0]를 1로 설정하여 if문을 돌지 않게 합니다.

2. 집(0,0)에서 학교(m,n)으로 가는 방법

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
d = [[1,0], [0,1]]
def dfs(x, y, dp, m, n):
    if y == n-1 and x == m-1 :
        return 1
    if dp[y][x] != 0:
        return dp[y][x]

    for i in range(2):
        ny = y + d[i][0]
        nx = x + d[i][1]

        if 0 <= ny < n and 0 <= nx < m:
            if dp[ny][nx] != -1:
                dp[y][x]+=dfs(nx,ny,dp,m,n)
    return dp[y][x]
def solution(m, n, puddles):
    dp = [[0 for _ in range(m)] for _ in range(n)]
    for p in puddles:
        x, y = p
        dp[y-1][x-1] = -1
    answer = dfs(0,0, dp, m, n)
    print(dp)
    return answer % 1000000007
print(solution(4, 3, [[2, 2]]))

(0,0)에서부터 dfs를 돌면서 dp배열에 값을 memoization 합니다. 이때, (m,n)에 도달하면 1을 리턴합니다. 

 

참고

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