[Programmers]Python_등굣길

문제

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 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개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

코드

def solution(m, n, puddles): #m = column, n = row
    figure = [[0] * m for _ in range(n)] #우선 n x m 크기의 격자를 만들어준다
    
    for row in range(n):
        for col in range(m):
            if (row, col) == (0, 0): #strat 지점은 항상 1이다
                figure[row][col] = 1
            elif [row + 1, col + 1] in puddles: #현재 지점이 puddle이라면 pass
                continue
            else:
                #각 위치로 갈 수 있는 경로는 왼쪽까지 갈 수 있는 경로와 위쪽까지 갈 수 있는 경로의 합과 같다
                figure[row][col] = figure[row - 1][col] + figure[row][col - 1]
                
    return figure[-1][-1] % 1000000007

 

진행 과정

예제 #1

m = 4

n = 3

puddles = [[2, 2]]

 

1) figure[0][0] = 1 #시작점은 1로 지정(시작점에서 시작해서 시작점으로 가는 경우는 항상 1이므로....)

2) figure[1][0] = 0 + 1 #왼쪽(1, -1)까지 갈 수 있는 경로 = 0, 위쪽(0, 0)까지 갈 수 있는 경로 = 1

3) figure[2][0] = 0 + 1 #왼쪽(2, -1)까지 갈 수 있는 경로 = 0, 위쪽(1, 0)까지 갈 수 있는 경로 = 1

4) figure[3][0] = 0 + 1 #왼쪽(3, -1)까지 갈 수 있는 경로 = 0, 위쪽(2, 0)까지 갈 수 있는 경로 = 1

5) figure[0][1] = 1 + 0 #왼쪽(0, 0)까지 갈 수 있는 경로 = 1, 위쪽(-1, 1)까지 갈 수 있는 경로 = 0

5) figure[1][1] = 0 #[1 + 1, 1 + 1] = [2, 2]이므로 puddle이다. 따라서 해당 지점으로 갈 수 있는 경우는 없다.

6) figure[2][1] = 1 + 0 #왼쪽(2, 0)까지 갈 수 있는 경로 = 1, 위쪽(1, 1)까지 갈 수 있는 경로 = 0

7) figure[3][1] = 1 + 1 #왼쪽(3, 0)까지 갈 수 있는 경로 = 1, 위쪽(2, 1)까지 갈 수 있는 경로 = 1

8) figure[0][2] = 1 + 0 #왼쪽(0, 1)까지 갈 수 있는 경로 = 1, 위쪽(-1, 2)까지 갈 수 있는 경로 = 0

9) figure[1][2] = 0 + 1 #왼쪽(1, 1)까지 갈 수 있는 경로 = 0, 위쪽(0, 2)까지 갈 수 있는 경로 = 1

10) figure[2][2] = 1 + 1 #왼쪽(2, 1)까지 갈 수 있는 경로 = 1, 위쪽(1, 2)까지 갈 수 있는 경로 = 1

11) figure[3][2] = 2 + 2 #왼쪽(3, 1)까지 갈 수 있는 경로 = 2, 위쪽(2, 2)까지 갈 수 있는 경로 = 2

 

어쩌다보니 문제 설명에 나온 그림과 행렬이 뒤바뀌었지만... 풀이상 똑같다.