[프로그래머스] 등굣길 c++

 

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42898

KEY

• 101 * 101 의 arr배열을 선언 한 후, 물 웅덩이가 있는 부분에 -1을 넣는다.
• 시작부분인 arr[1][1]에 1을 넣는다.

1	0	0	0
0	-1	0	0
0	0	0	0

 

• arr[i][j] = arr[i-1][j] + arr[i][j-1]의 점화식으로 arr[i][j]에 값을 넣어가며 최단경로의 가짓 수를 구할 수 있다.

1	1	1	1
1	-1	1	2
1	1	2	4

 

 

백트래킹으로 최단경로의 가짓수를 구하는 방식으로 풀면 테스트케이슨는 모두 통과했지만 전부 시간 초과가 발생한다.

격자의 크기가 100*100이나 되서 재귀로 푸는데에는 시간초과가 뜰 수 밖에 없다.

 

Dfs(백트래킹) - 시간초과

#include <string>
#include <vector>
#include <iostream>
using namespace std;
int M,N;
int dir[2][2] = {{0,1},{1,0}};
bool visited[101][101];
int arr[101][101];
long long answer;
 
void dfs(int x, int y){
    if(x==N && y==M){
        answer++;
        return;
    }
    for(int i=0;i<2;i++){
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if(visited[nx][ny])
            continue;
        if(nx>N || nx<0 || ny>M || ny<0)
            continue;
        if(arr[nx][ny] == 1)
            continue;
        visited[nx][ny] = true;
        dfs(nx,ny);
        visited[nx][ny] = false;
    }
}
int solution(int m, int n, vector<vector<int>> puddles) {
    N = m;
    M = n;
    
    for(int i=0;i<puddles.size();i++){
        arr[puddles[i][0]][puddles[i][1]] = 1;
    }
    
    dfs(1,1);
    return answer%1000000007;
}

 

Dp - 통과

#include <string>
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;
int arr[101][101];
int solution(int m, int n, vector<vector<int>> puddles) {
    //물에 잠긴 지역은 -1으로 만든다.
    for(int i=0;i<puddles.size();i++){
        arr[puddles[i][1]][puddles[i][0]] = -1;
    }
    
    arr[1][1] = 1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            int a=0;
            int b=0;
            if(arr[i][j] == -1)
                continue;
            if(arr[i-1][j] != -1){
                a = arr[i-1][j];
            }
            if(arr[i][j-1] != -1){
                b = arr[i][j-1];
            }
            arr[i][j] += (a+b) % 1000000007;
        }
    }
    return arr[n][m];
}