[Python | 파이썬] 등굣길 (프로그래머스 DYNAMIC PROGRAMMING)

[Python | 파이썬] 등굣길 (프로그래머스 DYNAMIC PROGRAMMING)

 

 

이 문제는 dynamic programming을 이용해서 풀 수도 있지만 BFS를 이용해서 풀 수도 있다.

움직이는 방향은 최단거리를 유지해야하므로 오른쪽으로 가거나 아래로 가야한다. 최단경로의 갯수를 리턴해야하므로 처음에 maps[0][0]에서의 경로의 갯수는 1으로 시작한다. 그리고 queue에 현재 좌표를 삽입하고, queue에 원소가 남아있을 때까지 반복문에서 매번 pop해주며 현재 좌표에서 오른쪽이나 아래쪽으로 이동가능하다면 queue에 그 좌표를 삽입한다. 또한 mapx[nx][ny] += maps[x][y]로 경로를 추가해준다.

dx = [0, 1]
dy = [1, 0]
from collections import deque
def solution(m, n, puddles):
    answer = 0
    maps = [[0] * m for _ in range(n)]
    maps[0][0] = 1
    q = deque([])
    q.append((0, 0))
    while q:
        x, y = q.popleft()
        for r in range(2):
            nx, ny = x + dx[r], y + dy[r]
            if 0 <= nx < n and 0 <= ny < m:
                if [ny+1, nx+1] in puddles:
                    continue
                maps[nx][ny] += maps[x][y]
                if (nx, ny) not in q:
                    q.append((nx, ny))
    answer = maps[n-1][m-1] % 1000000007
    return answer

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

프로그래머스