[동적 계획법] 등굣길

문제 설명

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

프로그래머스

문제 풀이

• 좌표 (1,1)에서 출발 해서 (n,m)으로 도착하는 최단 경로의 개수를 구하는 문제(문제에서는 m,n 이라 했는데 평소 n,m으로 습관이 되어있어서 n,m으로 도착하는 걸로 설정해서 품)
• 최단 경로로 도착하는 거리가 아닌 경로의 개수를 구하는거임
• visited 그래프에서 웅덩이인 부분은 -1로 미리 표시 (못 건넘)
• 오른쪽과 아래로만 이동 하니 이전 경로로 빠질 경우 x
• 1,1 에서 출발하면 어느 경로든 1가지는 생기는 것이므로 visited[1][1]=1로 설정
• 방문한 적 없는 장소라면 visited[x][y]의 값을 넣어주고 , 큐에 다음 위치를 넣어 줌
• 방문한 적 있는 장소라면 visited[nx][ny] + visited[x][y] , 이미 그 위치 값은 큐에 담겨져 있으므로 또 넣을 필요x

소스 코드

from collections import deque

dx = [0,1]
dy = [1,0]
def solution(m, n, puddles): # m은 가로, n이 세로
    visited =[ [0]*(m+1) for i in range(n+1)]
    for ip in puddles:
        a,b=ip
        visited[b][a]=-1
    q = deque()
    q.append([1,1])    
    visited[1][1]=1
    while(q):
        x,y = q.popleft()
        for i in range(2):
            nx = x + dx[i]
            ny = y + dy[i]
            if(nx>n or ny>m):
                continue
            if(visited[nx][ny]==-1):
                continue
            if(visited[nx][ny]==0):
                visited[nx][ny]=visited[x][y]
                q.append([nx,ny])
            else:
                visited[nx][ny]+=visited[x][y]
                
    return visited[n][m]%(int(1e9)+7) 	#1,000,000,007 로 나눴을 때의 나머지를 출력해야함

    
print(solution(4,3,[[2,2]]))