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

프로그래머스_등굣길

DP

def solution(m, n, puddles):
    dp = [[0]*(m+1) for _ in range(n+1)]
    puddles = [[p2,p1] for p1, p2 in puddles]
    
    dp[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 [i,j] in puddles:
                dp[i][j] = 0
            else:
                dp[i][j] = (dp[i-1][j] + dp[i][j-1])
                
    return dp[n][m]%1000000007

이 문제의 경우 x,y축이 다른 문제들과 다르게 되어있고 puddles가 바뀌어 입력되어 있으므로 주의해야한다
물이 잠긴 지역은 0으로 처리하고, 아닌 지역인 경우에는 도착할 수 있는 경우가 왼쪽or위쪽에서만 올 수 있으므로 왼쪽까지 오는 경로의 수+위쪽까지 오는 경로의 수 를 해주면 된다

BFS

from collections import deque
def solution(m, n, puddles):
    graph = [[0]*(m+1) for _ in range(n+1)]
    puddles = [[p2,p1] for p1, p2 in puddles]
    
    dx = [0,1]
    dy = [1,0]
    
    q = deque()
    q.append((1,1))
    graph[1][1] = 1
    while q:
        x, y = q.popleft()
        for k in range(2):
            nx = x+dx[k]
            ny = y+dy[k]
            if 0<=nx<=n and 0<=ny<=m:
                if [nx,ny] in puddles:
                    continue
                if (nx,ny) not in q:
                    q.append((nx,ny))
                graph[nx][ny] += graph[x][y]

    return graph[n][m]%1000000007

경로 문제여서 BFS로도 풀어봤는데, 정확성은 다 통과했지만 효율성 검사에서 2개정도 시간초과가 났다