Lv3. 등굣길 ( 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개 이하입니다.
- 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.
# 입출력 예
| m | n | puddles | return |
|---|---|---|---|
| 4 | 3 | [[2, 2]] | 4 |
입출력 예 설명
문제 해결 시 고려사항
- 최단 경로의 수를 구하기 위하 점화식의 작성
본 문제는 주어지는 크기의 격자모양 내에서 (1,1) 위치의 집으로부터 (m,n) 위치의 학교까지 갈 수 있는 최단 거리의 경우의 수를 구하는 문제이다. 하지만 격자 내에는 물 웅덩이가 존재하며 물 웅덩이의 위치로의 이동은 이루어 질 수 없다. 따라서 필자는 DP를 활용하여 물 웅덩이의 위치를 고려한 점화식 작성으로 문제를 해결하였다. 그 과정은 아래와 같다.
dp 값(경로의 수)를 담을 리스트와 문제에서 주어지는 격자 모양의 지도를 나타내기 위한 board 리스트를 생성
# dp, board 리스트 생성(0의 값 할당) dp = [[0]*(m+1) for _ in range(n+1)] board = [[0]*(m+1) for _ in range(n+1)]물 웅덩이(puddles)의 위치를 구분 짓기 위해 board에 -1의 값을 할당
# 웅덩이에 해당하는 위치를 구분짓기 위해 -1로 값 할당 for i in range(len(puddles)): board[(puddles[i][1])][(puddles[i][0])] = -1웅덩이를 피해 등교할 수 있는 경로의 수를 구하기 위한 탐색 실시
현재 위치가 시작 지점(집)이라면 1로 초기화
# 현재 위치가 시작 지점이라면 dp값을 1로 초기화 if i == 1 and j == 1: dp[i][j] = 1현재 위치가 웅덩이라면 dp 값에 대한 처리 없이 통과 => dp는 0의 값을 가져 이동할 수 없다는 의미
# 현재 위치가 웅덩이라면 dp 값에 변화를 주지 않고 통과(dp 값은 0) # 0은 해당 위치로 이동할 수 있는 경로가 없다는 의미를 가짐 elif board[i][j] == -1: continue현재 위치가 시작 지점과 웅덩이가 아니라면 현재 위치기 기준 좌측과 상단의 dp 값을 더하여 현재 위치까지의 경로의 수를 계산 => 최단 거리로 이동하기 위해서는 우측과 하단으로의 이동만 이루어져야 하기 때문
else: # 최단 거리로 움직이려면 우측과 하단으로의 이동만 이루어지기 때문에 # 현재 위치의 상단과 좌측의 dp 값을 더하여 경로의 수를 계산 dp[i][j] += (dp[i-1][j] % 1000000007 + dp[i][j-1] % 1000000007) % 1000000007
전체 코드
def solution(m, n, puddles):
# dp, board 리스트 생성(0의 값 할당)
dp = [[0]*(m+1) for _ in range(n+1)]
board = [[0]*(m+1) for _ in range(n+1)]
# 웅덩이에 해당하는 위치를 구분짓기 위해 -1로 값 할당
for i in range(len(puddles)):
board[(puddles[i][1])][(puddles[i][0])] = -1
# 웅덩이를 피해 등교할 수 있는 최단 루트 경우의 수 탐색
for i in range(1, n+1):
for j in range(1, m+1):
# 현재 위치가 시작 지점이라면 dp값을 1로 초기화
if i == 1 and j == 1:
dp[i][j] = 1
# 현재 위치가 웅덩이라면 dp 값에 변화를 주지 않고 통과(dp 값은 0)
# 0은 해당 위치로 이동할 수 있는 경로가 없다는 의미를 가짐
elif board[i][j] == -1:
continue
# 현재 위치가 웅덩이가 아니라면
else:
# 최단 거리로 움직이려면 우측과 하단으로의 이동만 이루어지기 때문에
# 현재 위치의 상단과 좌측의 dp 값을 더하여 경로의 수를 계산
dp[i][j] += (dp[i-1][j] % 1000000007 + dp[i][j-1] % 1000000007) % 1000000007
return dp[n][m]% 1000000007