[프로그래머스/파이썬] 등굣길

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

프로그래머스

문제 요약 : 물에 잠긴 지역을 피해 집에서 학교까지 가려고 할 때, 최단 거리의 개수를 구하라.

 

풀이 )

최단거리 개수 문제라서 BFS를 풀어야 하나 고민하다가 중고등학교 때 배웠던 방법이 떠올랐다.

https://m.blog.naver.com/parkhc1992/220669287080

[확률과 통계] 최단거리 경우의수

대충 이런 문제..

어차피 이 문제는 오른쪽이나 아래로 밖에 가지 못하기 때문에 왼쪽과 위쪽의 DP값을 더해주면 된다

 

틀린이유 1 :

처음에 테스트케이스는 풀리는데 코드를 제출하면 틀려서 이유가 뭐지 하고 봤는데 좌표를 잘못 잡고 있었다..

파이썬에서 2차 배열의 경우

[0,0] [0,1] [0,2] [0,3]

[1,0] [1,1] [1,2] [1,3]

[2,0] [2,1] [2,2] [2,3]

 

이런식으로 가는데 문제에서 [m,n]으로 된 것을 보고 착각했다..ㅠ 바보 탱이

def solution(m, n, puddles):
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    dp[1][1] = 1    # 시작 점 1
            
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if [j,i] in puddles : # 웅덩이는 0으로 변환 후 continue
                dp[i][j] = 0
                continue
                
            dp[i][j] += (dp[i - 1][j] + dp[i][j - 1]) % 1000000007

    return(dp[n][m])

틀린 이유 2 :

틀린 이유 1과 같다 웅덩이를 0으로 변환할 때에 

if [i,j] in puddles : dp[j][i] = 0 이라고 해서 틀림..ㅠ

좌표가 대칭된것인지 아닌것인지 확인하는게 중요했음

 

예전에도 DP문제에서 대칭된 좌표문제에서 애를 먹었는데 ㅋㅋ... 좀 나아져라 진짜