[프로그래머스] 등굣길

문제

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

프로그래머스

 

Level 4로 나와있지만, 학창 시절에 배웠던 걸 잘만 기억하면 Level 2 이하의 난이도가 된다.

---

 

주요 아이디어

최단 경로 경우의 수를 구하는 문제를 기억하는가?

기억이 안나면 보고 오자. (링크)

간단하게 요약하자면, x[i][j] 까지 도달하는 경우의 수는 x[i-1][j] 경우의 수 + x[i][j-1] 경우의 수이다.

 

예시.

예시로 나온 문제의 최단경로 경우의 수를 체크하면 다음과 같다.

최단경로 경우의 수

그렇다면 웅덩이가 있는 경우는 어떨까?

웅덩이가 존재하는 경우에는 해당 칸을 0으로 취급하고, 더하지 않으면 경우의 수를 올바르게 구할 수 있다.

---

코드 구현 (Python 3)

 

def solution(m, n, puddles):
    answer = 0
    # dp 리스트 2차원 리스트로 구성
    dp = [[0]*m for _ in range(n)]
    
    # 시작 위치 표시
    dp[0][0] = 1
    
    # 시작 위치부터 돌기
    for i in range(n):
        for j in range(m):
            up = [i-1, j]
            left = [i, j-1]
            
            # 웅덩이가 아닐 경우 & 시작 위치가 아닐 경우
            if ([j+1, i+1] not in puddles) and ((i, j) != (0,0)):
                dp[i][j] = (dp[up[0]][up[1]] + dp[left[0]][left[1]]) % 1000000007
    
    
    return dp[-1][-1]

 

 

 

제출 결과