(Python) 프로그래머스 - 등굣길

08 Mar 2022 in Algorithm on Programmers, Level3

[문제 링크]

풀이

def solution(m, n, puddles):
    graph = [[1] * m for _ in range(n)]
    # 웅덩이 0 처리
    for x, y in puddles:
        graph[y - 1][x - 1] = 0
    
    # 1행 웅덩이 이후 0처리
    for y in range(m):
        if graph[0][y] == 0:
            for k in range(y, m):
                graph[0][k] = 0
            break
            
    # 1열 웅덩이 이후 0처리
    for x in range(n):
        if graph[x][0] == 0:
            for k in range(x, n):
                graph[k][0] = 0
            break
    
    # dp 계산
    for x in range(1, n):
        for y in range(1, m):
            if graph[x][y] != 0:
                graph[x][y] = graph[x - 1][y] + graph[x][y - 1]

    return graph[n - 1][m - 1] % 1_000_000_007

처음에 bfs로 풀었는데 시간 초과가 발생했다.
시간 초과가 날 부분은 큐에 중복된 spot이 들어가서 여러번 계산하게 되는게 문제라고 판단 했고 dp로 전환했다.