[프로그래머스/Python] 등굣길
문제 정보
제목 : 등굣길
난이도 : Lv.3
사용 언어 : Python
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/42898
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 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 |
입출력 예 설명
나의 풀이
dp를 0으로 초기화 하고 처음 위치를 1로 정합니다. 편의를 위해 물에 잠긴 지역 좌표 리스트를 y,x 형태로 저장해줍니다.
1부터 n+1, 1부터 m+1까지 반복하는 이중 for루프를 이용해 해당 위치가 시작지점이나 물에 잠긴 지역이라면 continue를 하고, 아니라면 현재 위치를 기준으로 위쪽 경로의 수와 왼쪽 경로의 수를 저장하여 1,000,000,007로 나눈 나머지를 저장합니다. 반복이 종료되면 dp[n][m]을 answer에 저장하여 return합니다.
코드
def solution(m, n, puddles):
answer = 0
dp = [[0]*(m+1) for _ in range(n+1)] # dp 초기화
dp[1][1] = 1 # 처음 위치 1로 정함
puddles = [[y,x] for [x,y] in puddles] # 물에 잠긴 지역 좌표 y,x형태로 나타냄
for i in range(1,n+1):
for j in range(1,m+1):
if((i==1 and j==1) or ([i,j] in puddles)): # 처음위치or물에잠긴 지역이라면 continue
continue
else :
# 해당 위치까지 올 수 있는 경로 수 저장함.
# dp[i-1][j] : 아래쪽으로 움직인 경우
# dp[i][j-1] : 오른쪽으로 움직인 경우
dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007
answer = dp[n][m]
return answer