프로그래머스 등굣길 (파이썬)

DP, Level 3

 

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

 

문제 설명

물에 잠기지 않은 지역을 통해 등교

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)

가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)
격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수

오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return

 

제한사항
격자의 크기 m, n은 1 이상 100 이하인 자연수
m과 n이 모두 1인 경우는 없음
물에 잠긴 지역은 0개 이상 10개 이하
집과 학교가 물에 잠긴 경우는 없음

 

주의사항

웅덩이의 좌표는 m과 n 순서로 (평소 배열의 접근 방향과 반대)

 

첫번째 제출 코드 (정답)

def solution(m, n, puddles):
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    dp[1][1] = 1

    # 1열과 1행만 물 웅덩이 체크
    for j in range(2, m + 1):
        if [j, 1] in puddles:
            break
        dp[1][j] = 1

    for i in range(2, n + 1):
        if [1, i] in puddles:
            break
        dp[i][1] = 1

    for i in range(2, n + 1):
        for j in range(2, m + 1):
            if [j, i] in puddles:
                dp[i][j] = -1

    for i in range(2, n + 1):
        for j in range(2, m + 1):
            if dp[i][j] == -1:
                continue
            if dp[i - 1][j] == -1:
                dp[i][j] = dp[i][j - 1]
            elif dp[i][j - 1] == -1:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1])

    return (dp[n][m] % 1000000007)

덧셈 계산을 편하게 하기 위해 행과 열을 하나씩 추가

2행과 2열을 모두 1로 초기화

웅덩이가 있는 부분을 -1로 변경 

[i,j] 가 -1 이면 넘어감, [i,j] 주위에 웅덩이 있으면 좌측이나 위쪽 값 그대로  

 

정답 코드

def solution(m, n, puddles):
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    dp[1][1] = 1
    if puddles[0]:
        puddles = [[q, p] for [p, q] in puddles]

    for i in range(1, n+1):
        for j in range(1, m+1):
            # 집
            if i == 1 and j == 1:
                continue
            if [i,j] in puddles:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

    #for i in range(n+1):
        #print(dp[i])

    return (dp[n][m] % 1000000007)

 

웅덩이나 못가는 곳을 먼저 -1로 바꿔주는 것이 아님

웅덩이를 만나면 그 위치를 0으로 만들어 다음 계산에 영향을 미치지 않게 함