[프로그래머스/파이썬] 다이나믹프로그래밍 등굣길

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

알고리즘 분류

• 다이나믹프로그래밍

문제풀이

시간초과코드
def solution(m, n, puddles):
from collections import deque
dx=[1,0]
dy=[0,1]

kx=[-1,0]
ky=[0,-1]
graph=[[0]*m for i in range(n)]

for i in puddles:
    x,y=i
    graph[y-1][x-1]=-1
graph[0][0]=1

queue=deque()
queue.append((0,0))
while queue:
    x,y=queue.popleft()
    if x==n-1 and y==m-1:
        break
    for i in range(2):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx>=n or ny>=m:
            continue
        elif graph[nx][ny]==0:
            cnt=0
            for j in range(2):
                xx=nx+kx[j]
                yy=ny+ky[j]
                if xx<0 or yy<0:
                    continue 
                elif graph[xx][yy]!=-1:
                    cnt+=graph[xx][yy]
            graph[nx][ny]=cnt
        queue.append((nx,ny))

return (graph[n-1][m-1]%1000000007)

bfs두번 돌리다가 시간초과로 실패했다.

0으로 초기화한 가로, 세로를 한 줄씩 추가해주고 출발 지점인 집의 위치의 값은 1로 해준다.

각각의 좌표에서 왼쪽과 위 값을 더해나가면 된다.

graph=[[0, 0, 0, 0, 0], [0, 1, 1, 1, 1], [0, 1, 0, 1, 2], [0, 1, 1, 2, 4]]

소스코드

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

    for i in range(1,n+1):
        for j in range(1,m+1):
            if [j,i] in puddles:
                continue
            if i==1 and j==1:
                continue
            graph[i][j]=graph[i-1][j]+graph[i][j-1]
    return (graph[n][m]%1000000007)