[프로그래머스 | Lv3] 등굣길 (Python)

 

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

 

 

0으로 초기화된 dp 배열을 만들어주고, 집이 있는 자리는 1로 만들어준다.

그 후 1행 -> 2행 -> ... 으로 반복문을 돌면서

(오른쪽, 아래쪽으로만 가기 때문에 옆으로 건너가면서 모든 경우의 수를 계산할 수 있다.)

[x-1][y], [x][y-1]의 배열을 합한 값을 더해주면 된다.

 

# 프로그래머스 42898: 등굣길

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

    for x in range(1, n+1):
        for y in range(1, m+1):
            if x == 1 and y == 1:
                continue
            if [y, x] in puddles:
                continue
            dp[x][y] = dp[x-1][y] + dp[x][y-1] 

    return (dp[-1][-1]) % 1000000007

 

이 문제 푸느라 고생을 좀 했다...

 

1. 처음에 문제 이해 잘못해서 최단경로의 개수가 아니라 최단경로의 길이인 줄 알고

분명 다 맞는데 왜 모든 답이 틀리게 나오는거지 하고 한 시간동안 삽질했다ㅎ;;

2. 출제자가 물이 잠긴 지역의 좌표를 반대로 줬다;;

3. bfs로 풀다가 자꾸 시간 초과가 와다닥 떴다ㅠ