프로그래머스: 등굣길

문제

코딩테스트 연습 - 등굣길

 

문제 풀이

집에서 학교까지 가는 길은 MxN 일 때, 폭우로 인해 갈 수 없는 길이 있다. 이때, 등교를 할 수 있는 경우의 수를 반환하는 문제이다. 문제는 x, y에 따른 2차원 배열을 생성하여 방문하는 경로를 기록하는 방식으로 풀  수 있다.

 

 

 기존의 그래프에서 위의 그림과 같이 0을 추가한 DP 배열을 초기화한다. 그리고 처음 출발점인 집을 1로 초기화한 후 점화식인 `dp[x][y] = dp[x - 1][y] + dp[x][y - 1]`을 각 지점마다 웅덩이가 아닌지 확인하고 기록하면 된다. 점화식은 그림과 같이 하나의 좌표로부터 접근 가능한 경로는 위의 그림의 화살표와 같기 때문이다.

 

코드

def solution(m, n, puddles):
    answer = [[0] * (m + 1) for _ in range(n + 1)]
    answer[1][1] = 1

    for x in range(1, n + 1):
        for y in range(1, m + 1):
            if x == y == 1:
                continue

            if [y, x] in puddles:
                answer[x][y] = 0
            else:
                answer[x][y] = answer[x - 1][y] + answer[x][y - 1]
    return answer[-1][-1] % 1000000007