[프로그래머스] 등굣길 - python (레벨 3)

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

코딩테스트 연습 - 등굣길

풀이

문제를 보았을때 알수있는 힌트

오른쪽, 아래로만 움직이는 문제이며 웅덩이가 있는 곳은 지나가지 않는 문제이다.

dfs,bfs로 풀면 아마 시간 초과가 날 확률이 높을것이다.

이것은 dp로 풀어야한다.

시작하는 위치에서 오른쪽 왼쪽으로 이동시킬수있는 갯수를 추가하는 형식으로 진행하면 쉽게 풀 수 있는 문제이다.

 

def solution(m, n, puddles):
    answer = 0
    graph = [[0 for _ in range(m)] for _ in range(n)]
    
    for x,y in puddles:
        graph[y-1][x-1]=-1
    
    graph[0][0]=1
    for x in range(n):
        for y in range(m):
            # 오른쪽이 있는지 확인하기
            if graph[x][y]!=-1:
                if y+1<m and graph[x][y+1]!=-1:
                    graph[x][y+1] = (graph[x][y]+graph[x][y+1])%1000000007
                if x+1<n and graph[x+1][y]!=-1:
                    graph[x+1][y] = (graph[x][y] +graph[x+1][y])%1000000007
            
    answer=graph[n-1][m-1]
    return answer

https://github.com/dydwkd486/coding_test/blob/main/programmers/등굣길.py 

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리