[python 파이썬][프로그래머스] 등굣길(동적계획법)

v출처 : https://programmers.co.kr/learn/courses/30/lessons/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 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

m                                      n                                  puddles                             return

4

3

[[2, 2]]

4

입출력 예 설명

---

◆ 문제풀이

 

• 학교가 (i,j)라면 학교까지의 최적의 경로는 학교 윗칸(i-1 , j)까지의 최적의 경로와 학교 왼쪽칸(i, j+1)까지의 최적의 경로 합이다.
• 따라서 동적계획법에 따라 새로운 리스트를 만들어 경로를 기록한다.
• 집에서 어떤칸 까지의 최적의 경로는 어떤 칸의 윗칸과 왼쪽칸의 합인데 맨 위쪽칸들과(i=1인경우), 맨 왼쪽칸(j=1인 경우)인 경우에는 위쪽칸이 없거나 왼쪽칸이 없기때문에 더할 수가 없다.
• 따라서 가장 위쪽에 한줄 가장 왼쪽에 한줄을 만든다.
• 새로 만든 줄과 웅덩이를 특정한 값으로 설정하여 경로기록시 무시될수 있도록 한다.

 

◆ 코드1(새로만든 줄과 웅덩이를 'None'로 설정한 경우

def solution(m, n, puddles):
    answer = 0
    #외곽지역을 None로 설정
    memo=[[0 if i !=0 else None for i in range(m+1)] for j in range(n+1)] 
    for i in range(len(memo[0])): 
        memo[0][i] = None
    memo[1][1] = 1 #집       
    for i in puddles: #웅덩이 None로 설정'
        memo[i[1]][i[0]] = None
    # 윗칸과 왼쪽칸까지의 최적 경로의 수 합이 현재칸까지의 최적 경로의 수   
    for k in range(1,n+1):
        for j in range(1,m+1):
            if memo[k][j] is None: #웅덩이를 만났을때    
                continue
            if memo[k][j-1] is None and memo[k-1][j] is None: #윗쪽과 왼쪽이 None라면 현재칸도 None
                memo[k][j] is None
            elif memo[k-1][j] is None: #위쪽칸이 None일때 왼쪽칸이 현재칸의 경로의 수
                memo[k][j] =memo[k][j-1]
            elif memo[k][j-1] is None: #왼쪽칸이 None일때 위쪽칸이 현재칸의 경로의 수
                memo[k][j] =memo[k-1][j]
            else:
                memo[k][j] = memo[k-1][j] + memo[k][j-1] # 현재칸의 경로 = 윗칸과 왼쪽칸까지의 최적 경로의 수 합
    return memo[-1][-1] % 1000000007

 

이 경우 None의 위치에 따라 하나하나 조건을 하나하나 다 설정해 주어야하기 때문에 None대신에 0을 설정하여 코드를 만들어 보았다.

 

 

◆ 코드2(새로만든 줄과 웅덩이를 '0'로 설정한 경우

def solution(m, n, puddles):
    answer = 0
    memo=[[0 for i in range(m+1)] for j in range(n+1)] 
    memo[1][1] = 1 #집       
    print(memo)
    for k in range(1,n+1):
        for j in range(1,m+1):
            if [j,k] in puddles:
                continue
            if k==1 and j==1:
                continue
            memo[k][j] = memo[k-1][j] + memo[k][j-1]
    return memo[-1][-1] % 1000000007