Programmers 등굣길(동적계획법) - Python

문제 보기

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

프로그래머스

 

초기 코드

def solution(m, n, puddles):
    answer = 0
    visited = [[0 for _ in range(m)] for _ in range(n)] # 물 웅덩이 체크
    dp = [[0 for _ in range(m)] for _ in range(n)]
    for water in puddles:
        visited[water[1]-1][water[0]-1] = 1 # 물 웅덩이 부분 1로 체크
        
    for i in range(m): #윗 변 1로 체크
        if visited[0][i] == 0:
            dp[0][i] = 1
            
        else:
            for j in range(i,m): #물 웅덩이 있으면 다음 좌표부터 끝까지 0
                dp[0][j] = 0
                break
            break
    for i in range(n):
        if visited[i][0] == 1:
            for j in range(i,n):
                dp[i][0] = 0
                break
            break
        else:
            dp[i][0] = 1
    
    for j in range(n):
        for i in range(m):
            if i != 0 and j != 0 and visited[j][i] == 0: # 인덱스가 0이 아니고 방문체크가 0이면 계산
                dp[j][i] = dp[j-1][i] + dp[j][i-1]
            elif visited[j][i] == 1:
                dp[j][i] = 0
    return dp[n-1][m-1]%1000000007

 

윗 변과 왼쪽 변에서 물 웅덩이가 있을 때 다음 좌표부터 계속 0이라는 것을 캐치하지 못했다..

힌트를 보고 나서 깨달았다,,, 문제풀이에 급급하지 않고 숲을 봐야겠다...

코드를 더 깔끔하고 간편하게 적어보는 노력도 필요해보인다

 

결과 코드

def solution(m, n, puddles):
    dp = [[0] * (m + 1) for _ in range(n + 1)] # dp 테이블 초기화
    dp[1][1] = 1
    
    for i, j in puddles: # 웅덩이가 있는 곳은 -1로 표시
        dp[j][i] = -1
        
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if dp[i][j] == -1: # 웅덩이이면
                dp[i][j] = 0 # 이후 값에 영향을 주지 않게 하기 위해 0으로 바꾸고
                continue # 건너뜀
                
            # 위에서 오는 경우와 왼쪽에서 오는 경우를 더해줌
            dp[i][j] += (dp[i - 1][j] + dp[i][j - 1]) % 1000000007
            
    return(dp[n][m])