[Level 3] 등굣길

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

코딩테스트 연습 - 등굣길

---

접근

최소로 가기위해서는 웅덩이를 피해 오른쪽 또는 아래로만 이동해야한다.

따라서 각 지점으로 올 수 있는 경우의 수를 메모를 해둔다. 즉, 왼쪽과 위의 경로에 대한 경우의 수를 더해주도록 한다.

 

구현

시작점부터 도착지점까지 경로에 대한 경우의 수를 구한다.

만약 현재 위치가 puddles에 포함되어있다면 continue하고,

그렇지 않다면 현재 경우의 수를 왼쪽 길과 위에서 오는 길을 더해서 메모를 해둔다.

이렇게 되면 도착지점에 최소 경로의 수가 저장된다.

for i in range(1, n+1):
        for j in range(1, m+1):
            if i == 1 and j == 1:
                continue
            if [j, i] in puddles:
                continue
            else:
                visited[i][j] = visited[i-1][j] + visited[i][j-1]

---

전체 코드

def solution(m, n, puddles):
    answer = 0
    visited = [[0 for _ in range(m+1)] for _ in range(n+1)]
    visited[1][1] = 1
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            if i == 1 and j == 1:
                continue
            if [j, i] in puddles:
                continue
            else:
                visited[i][j] = visited[i-1][j] + visited[i][j-1]
    answer = visited[n][m]
    return answer%1000000007