[프로그래머스] 등굣길

 

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

코딩테스트 연습 - 등굣길

 

 

< 문제 설명 >

집에서 학교까지 가는 최단경로의 개수를 구해서 리턴하라.

단, 중간에 물 웅덩이가 있음. 물 웅덩이는 지나갈 수 없으며,

이동은 오른쪽과 아래로만 가능하다.

 

 

< 문제 이해 >

요런 문제 확통에서 많이 봤던 거라 팩토리얼로 풀어봤더니 바로 빠꾸먹음ㅎㅎ

dp문제이다.

한 칸을 기준으로 윗 칸과 왼쪽 칸의 최단경로 개수를 더해주면 현재 칸의 최단경로의 개수를 구할 수 있다.

집으로 표시되어있는 칸은 1로 설정한다.

이 때, 좌표를 순서를 바꾸어주는 것이 중요하다!

 

 

< 문제 풀이 >

def solution(m, n, puddles):
    puddles = [[y,x] for x,y in puddles]		# x,y 좌표 바꿔주기
    dp = [[0]*(m+1) for i in range(n+1)]		# (m+1)x(n+1)의 빈 배열 만들어주기
        
    dp[1][1] = 1					# 집이 있는 위치는 1로 설정
    
    for i in range(1,n+1):
        for j in range(1,m+1):
            if [i,j] == [1,1] or [i,j] in puddles: continue	# 집 위치이거나 물 웅덩이면 패스
            dp[i][j] = dp[i-1][j] + dp[i][j-1]			# 현재 위치의 위와 왼쪽 위치의 값을 합한다.
    
    return dp[n][m] % 1000000007