[프로그래머] 등굣길 - python 파이썬

문제

 

 

 

일단 이 문제는 dp를 통해서 풀어주는데 dp에 어떤 값을 저장하느냐가 관건인 문제이다.

 

이 문제는 최단 경로의 개수를 구하는 문제이기 때문에 dp에는 위쪽과 왼쪽에서의 경로의 수를 저장해주면 된다.

 

그렇기때문에

 

dp[i][j] = dp[i-1][j] + dp[i][j-1] 

 

가 된다.

 

이때 물웅덩이에 해당되는 좌표는 0을 넣어주어 처리해주면 된다.

 

또한 [1,1]의 좌표값을 for문이 시작하기 전에 1로 초기화 해준 후 for문 안에서 다시 0으로 바뀌지 않도록 예외처리를 해주어야한다.

 

 

 

그리고 문제를 보면 알겠지만 puddles 좌표의 x,y좌표 값이 우리가 사용하는 이중리스트의 좌표와는 반대로 주어졌기 때문에 이를 바꾸어 주어야한다.

 

puddles = [[q,p] for [p,q] in puddles]

 

이런식으로 x,y 좌표의 위치를 서로 바꾸어 주면된다

 

 

 

전체코드

def solution(m, n, puddles):
    #웅덩이 있는 곳 좌표 반대로 해주어야함
    puddles = [[q,p] for [p,q] in puddles] 

    dp = [[0]*(m+1) for _ in range(n+1)]
    #첫번쨰 좌표값 설정
    dp[1][1] = 1
    
    for i in range(1,n+1):
        for j in range(1,m+1):
            #설정해둔 초기값이 다시 0으로 초기화 되지 않기위한 예외처리
            if i == 1 and j == 1: continue
            #물 웅덩이 부분은 0으로 처리
            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

 

 

 

 

문제와 이중리스트의 좌표위치가 반대라는 점 그리고 점화식을 세우는 것이 가장 중요한 문제였던 것 같다.