프로그래머스 등굣길
문제
https://programmers.co.kr/learn/courses/30/lessons/42898#
코드
cpp
#include <string>
#include <vector>
#define N 1000000007
using namespace std;
int solution(int m, int n, vector<vector<int>> puddles) {
int answer = 0;
vector<vector<int>> dp(n,vector<int>(m,0));
for(auto i: puddles)
dp[i[1]-1][i[0]-1]=-1;
dp[0][0]=1;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if((i==0&&j==0)||dp[i][j]==-1) continue;
if(dp[i-1][j]==-1||i==0) dp[i][j]=dp[i][j-1];
else if(dp[i][j-1]==-1||j==0) dp[i][j]=dp[i-1][j];
else dp[i][j]=dp[i-1][j]%N+dp[i][j-1]%N;
}
}
answer=dp[n-1][m-1]%N;
return answer;
}
python
def solution(m, n, puddles):
answer = 0
dp = [[0]*(m+1) for _ in range(n+1)]
dp[1][1] = 1
for x, y in puddles:
dp[y][x] = -1
for i in range(1, n+1):
for j in range(1, m+1):
if dp[i][j] == -1:
dp[i][j] = 0
continue
if i == j == 1:
continue
dp[i][j] = dp[i-1][j]+dp[i][j-1]
return dp[n][m]%1000000007
풀이
집의 위치는 (1,1)로 고정되있고 학교의 위치는 (m,n)으로 고정되있을 때 집에서 학교까지 가는 최단경로의 수를 구하는 문제입니다. 개인적으로 n,m위치가 바뀐게 좀 불편했습니다
집에서 출발해서 오른쪽과 아래쪽으로만 움직이면 항상 최단경로이고 물웅덩이 예외처리를 해주면 문제는 어렵지 않게 풀 수 있습니다
코드를 보시면 물웅덩이는 -1로 표시해서 예외처리를 해주고 (0,0)에 1을 넣어준 다음 이중for문으로 dp테이블을 돌면서 만약 위쪽에 물웅덩이가 있거나 i가 0이라면 왼쪽값을 복사하고 왼쪽에 물웅덩이가 있거나 j가 0이라면 위 값을 복사합니다. 그게 아니라면 위의 값과 왼쪽값을 1,000,000,007로 나눠주면서 더해주면 됩니다.
Author And Source
이 문제에 관하여(프로그래머스 등굣길), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@josajang98/등굣길저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)