[프로그래머스] (동적계획법[Dynamic Programming]) - 42898 등굣길

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

m	n	puddles	return
4	3	[[2, 2]]	4

입출력 예 설명

---

문제풀이

def solution(m, n, puddles):
    # 행열 만들기
    dp = [[-1 for _ in range(m+1)] for _ in range(n+1)] 
    
    for puddle in puddles:
        dp[puddle[1]][puddle[0]]=0
    
    check=False # 1행, 1열 도중에 puddle이 있는지 확인을 위해
    # 도중에 puddle이 없는한 1로 처리
    for i in range(1,n+1):
        if dp[i][1]==0: check=True
        
        if check: dp[i][1]=0
        else: dp[i][1]=1
        
    check=False # 1행, 1열 도중에 puddle이 있는지 확인을 위해
    # 도중에 puddle이 없는한 1로 처리
    for i in range(1,m+1):
        if dp[1][i]==0: check=True
        
        if check: dp[1][i]=0
        else: dp[1][i]=1

    # 2행 2열부터 왼쪽과 위에 해당하는 값을 더하여 최신화 진행
    for i in range(2,n+1):
        for j in range(2,m+1):
            if dp[i][j]==0: continue
            else:
                dp[i][j]=dp[i-1][j]+dp[i][j-1]

    return dp[-1][-1]%1000000007

# print(solution(4,3,[[2, 2]]))

# 프로그래머스 -님이 올리셨던 반례 참고
#https://school.programmers.co.kr/questions/15698?question=15698

# print(solution(2, 2, []), 2)
# print(solution(3, 3, []), 6)
# print(solution(3, 3, [[2, 2]]), 2)
# print(solution(3, 3, [[2, 3]]), 3)
# print(solution(3, 3, [[1, 3]]), 5)
# print(solution(3, 3, [[1, 3], [3, 1]]), 4)
# print(solution(3, 3, [[1, 3], [3, 1], [2, 3]]), 2)
# print(solution(3, 3, [[1, 3], [3, 1], [2, 3], [2, 1]]), 1)
# print(solution(7, 4, [[2, 1], [2, 2], [2, 3], [4, 2], [4, 3], [4, 4], [6, 2], [6, 3]]), 0) # 이 값이 잘 나오면 테스트1, 테스트9 통과, 위로 가면 안됨
# print(solution(4, 4, [[3, 2], [2, 4]]), 7)
# print(solution(100, 100, []), 690285631)

반례 필요하신분은 아래 Reference에 프로그래머스 '-님'이 올리셨던 반례 참고!

 

Reference

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

프로그래머스

https://school.programmers.co.kr/questions/15698?question=15698 

프로그래머스