문제 설명
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 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개 이하입니다.
집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.
문제 풀이
처음에 문제를 잘못 읽어 최소 경로의 수를 찾는 문제로 알아서 dfs를 사용한 최소 경로 찾기를 했었는데...알고보니 총 경로의 수 였다..🤦♂️
(문제를 똑바로 읽자!!!)
그리고 저번 부터 문제를 보면 직접 연습장에 손으로 한번 해보면서 거기서 알고리즘을 도출하는 방법을 사용하고 있는데 마찬가지로 직접 예제를 손으로 그려 올 수 있는 경로를 찾다 보니,
위의 칸에서 올 수 있는 경로 + 왼쪽에서 올 수 있는 경로가 현재 위치까지 도달할 수 있는 경로인걸 알았다.
웅덩이가 있으니 웅덩이는 갈 수 없으므로 0으로 리셋 시켜주는 방식의 알고리즘을 찾았다.
- map을 만들고 시작점만 1로 하고 나머지를 0으로 리셋.
- map을 돌며 위쪽 경로 + 왼쪽 경로를 해줌.
- 웅덩이가 있으면 0 으로 리셋.
def solution(m, n, puddles):
maps = [[0]*(m+1) for _ in range(n+1)]
maps[1][1] = 1
for x in range (1,m+1):
for y in range (1,n+1):
if x == 1 and y == 1:
continue
if [x,y] in puddles:
maps[y][x] = 0
else:
maps[y][x] += maps[y-1][x] + maps[y][x-1]
answer = (maps[n][m]) % 1000000007
return answer