https://programmers.co.kr/learn/courses/30/lessons/42898
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.
아래 그림은 m = 4, n = 3 인 경우입니다.
가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.
격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다.
m n puddles return
4 3 [[2, 2]] 4
오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.
격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
물에 잠긴 지역은 0개 이상 10개 이하입니다.
집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.
푸는 방법이 전혀 생각이 안났다; 알고보니 옛날에 어렸을 때 수학 시간에 배웠던 최단거리 경로 경우의 수를 이용하는 문제였다... 양 가로 세로 변들에 1씩 주고 만나는 길은 각 경로 수를 더해주면 됐다. 기본 초기화 값을 0으로 주고 침수 지역은 0으로 만들어 주는 아이디어를 배웠다.
def solution(m, n, puddles):
# 인덱스는 0부터 시작하지만 문제 좌표는 1,1 부터 시작하므로
# 그리고 해당 칸의 최적 경로 수는 왼쪽 칸과 위쪽 칸의 수를 더한 수인데
# 맨 왼쪽과 맨 위쪽 칸들은 더해줄 것이 없는 부분은 0으로 해주기 위해
# 사이즈 1씩 더 크게 만들어 줌
path = [ [0 for i in range(m+1)] for j in range(n+1)]
# 집이 있는 곳 최소 경로 1로 시작
path[1][1] = 1
for i in range(1, n+1):
for j in range(1, m+1):
# 집 위치는 계산 필요 없음
if i == 1 and j == 1:
continue
# 해당 위치가 침수 지역일 경우 0으로 남겨둠
# 여기 인접 칸은 0이 더해져서 경로 수에 추가 안됨
if [j, i] in puddles:
continue
# 해당 칸까지의 최적 경로 수는
# 해당 칸의 왼쪽 칸과 위쪽 칸의 최적 경로 수의 합
path[i][j] = path[i-1][j] + path[i][j-1]
return path[n][m] % 1000000007