[프로그래머스] level3 등굣길 파이썬

 

풀이시간 : 30분

체감 난이도: level2

 

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

프로그래머스

 

 

 

※ 주의

-  puddles 가 컴퓨터 index 접근인 [1,1]이 아니라 [2,2]로 되어있다. 시작 위치도 [1,1]이다. 

 

※ 접근법

1. 동적 프로그래밍 -> 최단거리를 구하는 것도 아니고, 갈 수 있는 경로를 모두 구하는 것.

2. 동서남북을 확인하여 지금까지 왔던 값을 모두 더해주면 내가 현재 지점까지 올 수 있는 모든 경우의 수가 된다. 

3. 동서남북을 확인할 때 그래프르를 벗어나는 지점이랑 puddle가 아닌지만 확인. 

 

 

 

def solution(m, n, puddles):
    answer = 0
    # 갈 수 있는 경로 수를 저장하기 위한 그래프 초기화
    graph = [[0 for _ in range(m+1)] for i in range(n+1)]
    
    #동서남북
    mx = [1, -1 ,0 ,0]
    my = [0, 0, 1, -1]
    
    for y in range(1, n+1):
        for x in range(1, m+1):
        	# 시작점 초기화
            if [x,y] == [1,1]:
                graph[y][x] = 1
                continue
            
            # 동서남북을 모두 확인하며 각각 값을 모두 sum
            count = 0
            for dx, dy in zip(mx, my):
            	# 그래프를 벗어나는지 확인, 확인하는 지점이 푸들이 아닌지 확인
                if x+dx <= m and y+dy <= n and [x+dx, y+dy] not in puddles:
                    count += graph[y+dy][x+dx]
            # 해당 지점까지 올 수 있는 방법들 모두 더한다
            graph[y][x] = count
    return graph[n][m] % 1000000007