[프로그래머스] 파이썬 문제풀이 - 등굣길

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

프로그래머스

 

첫 풀이

1.  dfs 방식으로 첫 시도를 해봤다

2. 좌표 방식이 헷갈려서 실패했다

 

#최단경로 m+n-2
from collections import deque
def solution(m, n, puddles):
    answer = 0
    cnt=0
    local=[[0 for _ in range(m+1)] for _ in range(n+1)]
    for i in puddles:
        local[i[0]][i[1]]=1
    q=deque()
    q.append((1,1))
    while q:
        print(q)
        xy=q.popleft()
        
        if xy[0]==m and xy[1]==n:
            cnt+=1
        elif local[xy[0]][xy[1]]==0:
            if xy[0]+1<m and xy[1]<n:
                q.append((xy[0]+1,xy[1]))
            if xy[0]<m and xy[1]+1<n:
                q.append((xy[0],xy[1]+1))  
                   
    return cnt%1000000007

 

더 나은 답안

1. 2차원 dp테이블을 사용해 다이나믹 방식으로 풀어봤다

2. 웅덩이가 있는곳은 dp테이블에 -1로 표시해둔다

3. dp 테이블을 탐색할 때 웅덩이가 있는곳은 0으로 바꿔 경우의 수에 영향이 없게 만든다

 

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

    for i in range(1,n+1):
        for j in range(1,m+1):
            if dp[i][j]==-1:
                dp[i][j]=0
            else:
                dp[i][j]+=(dp[i-1][j]+dp[i][j-1])%1000000007
                   
    return dp[n][m]

 

배운 점

1. 2차원리스트에서는 좌표를 신경써야한다

dp=[[1,2,3],

[4,5,6]]

리스트가 있을때 dp[1] -> [4,5,6]] 처럼 먼저 행으로 접근을 하기 때문이다

흔히 수학계에서 사용하는 dp[1][2]에서 (1,2) 좌표와는 반대로 생각해야한다.