등굣길

문제

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

코딩테스트 연습 - 등굣길

---

풀이

DP를 사용해 푸는 문제이다. 문제에서 이동은 오른쪽과 아래쪽으로만 가능하다고 했으니, 한 지점까지 올 수 있는 가능한 경로는 그 지점의 위와 왼쪽칸으로부터이다. 따라서 각 칸마다 그 칸까지 도달가능한 경로의 수를 저장하면 된다.

grid라는 n x m 2차원 리스트를 만들어 (0,0)에 1을 넣고, puddle에는 -1을 넣는다. 그 후, 이중for문으로 탐색하며 탐색한 지점이 puddle이 아니라면(puddle이면 애초에 지나갈 수 없으니 갱신이 불필요하다.) 왼쪽과 위쪽 칸의 index가 리스트의 index를 벗어나지 않는지 체크한다. 그리고 왼쪽과 위쪽 칸이 역시 puddle이 아닌지 확인하고 해당 칸에 더해주면 된다.

def solution(m, n, puddles):

    if m == 1 or n == 1:
        if len(puddles) == 0:
            return 1
        else:
            return 0
        
    answer = 0
    grid = [[0 for _ in range(m)] for _ in range(n)]
    grid[0][0] = 1
    for x, y in puddles:
        grid[y-1][x-1] = -1
    
    for i in range(n):
        for j in range(m):
            if grid[i][j] != -1:
                if j-1 in range(m) and grid[i][j-1] != -1:
                    grid[i][j] = (grid[i][j]+ grid[i][j-1]) % 1000000007
                if i-1 in range(n) and grid[i-1][j] != -1:
                    grid[i][j] = (grid[i][j]+ grid[i-1][j]) % 1000000007
    
    answer = grid[n-1][m-1]

    return answer