[Python/프로그래머스] 등굣길_DP

 

 

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

코딩테스트 연습 - 등굣길

 

 

---

 

 

 

문제 설명 : 

 

 

왼쪽 그림과 같이 진행된다.

(1,1)에서 시작하여 우측, 아래로 이동한다.

 

경로의 개수를 반환하는 것으로 

왼쪽과 위의 합을 새로운 값으로 지정한다. 

 

중간에 웅덩이는 무시하고 넘어간다.

 

도착 위치의 값을 반환하면 된다.

 

 

 

 

 

 

 

코드 : 

def solution(m, n, puddles):
    answer = 0
    # puddle 이 (m,n)으로 주어진다. 
    graph = [[0]*(m+1) for i in range(n+1)]
    
    for i in range(1,n+1) :
        for j in range(1,m+1) :
            if i == 1 and j == 1 : # 시작점 
                graph[1][1] = 1 
            elif [j,i] not in puddles : # 웅덩이가 아닌곳이라면 
                graph[i][j] = graph[i-1][j] + graph[i][j-1]
    return graph[n][m] % 1000000007

 

 

이중 for문 밖에서 graph[1][1] =1 을 하면 

이중 for문을 돌면서 다시 값이 변경되므로 < (graph[i-1][j] + graph[i][j-1] ==0) 이므로 0으로 변경 >

이중 for문 안에서 i == 1, j ==1 일 때 설정을 해주어야한다. 

 

 

시작점(graph[1][1])을 1로 설정한다는 것 잊지말자 

+ 웅덩이는 [m,n] 순서로 주어진다. 

 

 

참고 블로그 :

 

https://jiwon-coding.tistory.com/124

[프로그래머스] 등굣길 / 파이썬(python)

 

 

복습 : 

✅ 20220620

✅ 20220622

✅ 20220624

✅ 20220626