[동적계획법(Dynamic Programming)] 등굣길

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

코딩테스트 연습 - 등굣길

 

어릴 때 학교 수학시간에 배웠었던, 최단거리 경우의수 문제이다.

아래 숫자들은 각 지점에 대한 최단거리로 도달가능한 경우의 수 개수이다.

 

1. 2차원 빈 리스트를 하나 만든다.

2. 시작점은 1로 한다.

3. 웅덩이는 0으로 한다.

4. 가로 첫번째 줄, 세로 첫번째 줄에 대해, 웅덩이를 만나기 전까지는 1, 웅덩이를 만난후에는 0으로 설정해준다.

5. 모든 나머지 칸들에 대해 경우의 수를 구해준다.

def solution(m, n, puddles):
    arr = [[None for j in range(m)] for i in range(n)]
    arr[0][0] = 1
    for i in puddles:
        arr[i[1]-1][i[0]-1] = 0
    c = 1
    for i in range(n):
        if arr[i][0] == 0:
            c = 0
        arr[i][0] = c
    c = 1
    for i in range(m):
        if arr[0][i] == 0:
            c = 0
        arr[0][i] = c 
    for x in range(1, n):
        for y in range(1, m):
            if arr[x][y] == None:
                arr[x][y] = arr[x-1][y] + arr[x][y-1]
    return arr[n-1][m-1]%1000000007