[프로그래머스] 등굣길 (C++)

👓 문제 설명

---

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

입출력 예

m	n	puddles	return
4	3	[[2, 2]]	4

입출력 예 설명

---

💣 제한 사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

---

🚨 접근 방법

처음 시도했던 풀이는 DFS를 이용하여 (m,n)지점에 도착하는 경우의 수를 구하였다.
하지만 시간초과가 대부분의 테스트케이스에서 발생하여 DP로 다시 풀었다.

우선 물웅덩이가 존재하는 구역을 arr배열에서 -1로 초기화해주었다.
또한 문제 특성 상, 방향은 아래, 오른쪽 두가지로만 이동이 가능하다.
따라서 1행과 1열에서 물웅덩이가 존재하면 그 지점부터 [1][n] or [m][1] 까지의 지점은 최단경로에 포함될 수 없으므로 이 지점으로 가는 경우의 수는 0으로 처리하면 된다.

또한 문제에서 x,y좌표를 반대로 주었다. 이 부분때문에 1시간을 소비했다.. 문제 잘 보자..

---

🚈 초키코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int answer=0,ex,ey;
int arr[101][101];
bool check[101][101];
void dfs(int sx,int sy){
    // 집 도착 시 
    if(sx==ex&&sy==ey){
        answer++;
        answer%=1000000007;
        return;
    }
        
    // 오른쪽
    if(sx>=1&&sx<=ex&&sy>=1&&sy+1<=ey&&!check[sx][sy+1]&&arr[sx][sy+1]==0){
        check[sx][sy+1]=true;
        //cout<<sx<<" "<<sy+1<<"\n";
        dfs(sx,sy+1);
        check[sx][sy+1]=false;
    }
    // 아래
    if(sx>=1&&sx+1<=ex&&sy>=1&&sy<=ey&&!check[sx+1][sy]&&arr[sx+1][sy]==0){
        check[sx+1][sy]=true;
        //cout<<sx+1<<" "<<sy<<"\n";
        dfs(sx+1,sy);
        check[sx+1][sy]=false;
    }   
}


int solution(int m, int n, vector<vector<int>> puddles) {
    for(int i=0;i<puddles.size();i++){
        arr[puddles[i][0]][puddles[i][1]]=1;
        //cout<<arr[puddles[i][0]][puddles[i][1]]<<" ";
    }
    ex=n;
    ey=m;
    check[1][1]=true;
    dfs(1,1);
    return answer;
}

초기 코드 --> DFS 실패

🚈 제출코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;

// (4,3) 이 집에 있음 

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    int arr[101][101]={0,};
    int dp[101][101]={0,};
    for(int i=0;i<puddles.size();i++){
        arr[puddles[i][0]][puddles[i][1]]=-1;
    }
    for(int i=2;i<=m;i++){
        if(arr[i][1]!=-1){
            dp[i][1]=1;    
        }
        else{
            break;
        }
    }
    for(int i=2;i<=n;i++){
        if(arr[1][i]!=-1){
            dp[1][i]=1;    
        }
        else{
            break;
        }
    }
    for(int i=2;i<=m;i++){
        for(int j=2;j<=n;j++){
            if(arr[i][j]==-1)continue;
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007;
            //cout<<i<<" "<<j<<" "<<up_cnt<<" "<<right_cnt<<"\n";
        }
    }
    return dp[m][n];
}