등굣길

 

#include <string>
#include <vector>

using namespace std;

int graph[101][101];
int gox[4]={1, 0, -1, 0};
int goy[4]={0, 1, 0, -1};
int ans = 0;
int garo;
int sero;

#define MAX 1000000

void dfs(int m, int n, int cost, int dir) {
    //리턴조건: 끝에 다다랐을 때
    if(m==1 && n==1) {
        //값이 아무것도 없다면, 초기화
        if(graph[1][1] == MAX) {
            ans++;
            graph[1][1] = cost;
            return;
        }
        else {
        //만일 새로온게 기존값보다 작다면, 이를 새 값으로 갱신
        //같다면, ans를 1 추가
        //크다면, 그냥 버림
            if(graph[1][1] > cost) {
                graph[1][1] = cost;
                ans = 1;
                return;
            }
            else if(graph[1][1] == cost) {
                ans++;
                return;
            }
        }
    }
    //또는, 현재값이 graph의 값보다 작을 때
    if(cost > graph[n][m]) {
        return;
    }
    
    graph[n][m] = cost;
    
    //m-4-가로, n-3-세로
    //4가지 방향 중, 후보를 조사한다.
    for(int i=0; i<4; i++) {
        int nextx = m+gox[i];
        int nexty = n+goy[i];
        //범위를 나가거나, 웅덩이에 빠지게 되면 pass
        if (nextx < 1 || nextx > garo ||
            nexty < 1 || nexty > sero ||
            graph[nexty][nextx] == -1)
            continue;
        //다시 돌아가게 되는 경우, pass 
     //   if(graph[nexty][nextx] >= cost)
     //       continue;
        
        dfs(nextx, nexty, cost+1, i);
    }
}

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    garo = m;
    sero = n;
    for(int i=1; i<=100; i++) {
        for(int j=1; j<=100; j++) {
            graph[i][j] = MAX;
        }
    }
    for(int i=0; i<puddles.size(); i++) {
        graph[puddles[i][1]][puddles[i][0]] = -1;
    }
    
    dfs(m, n, 0, -1);
    return ans%1000000007;
}

실패작

 

아래는 성공작.

자세히보면, 오른쪽과 아래로만 움직여서 갈 수 있는 경로를 탐색해야 한다

위의 코드는 4방향을 다움직여야 하는 조건을 상정하고 있다.

따라서, 이때문인진 모르겠는데 정확성테스트는 다 맞지만 효율성테스트는 다 떨어진다.

맨 처음에는 4방향인줄 알고 풀었는데, 아니었다.

#include <string>
#include <vector>

using namespace std;

int graph[101][101] = {0,};
int pud[101][101] = {0,};
int ans = 0;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    for(auto a:puddles) {
        pud[a[1]][a[0]] = 1;
    }
    graph[0][1] = 1;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            //웅덩이면, 갈 경우의수 0
            if(pud[i][j] == 1)
                graph[i][j] = 0;
            //아니면, 갈 수 있는 경우의 수는 
            else {
                graph[i][j] = (graph[i-1][j] + graph[i][j-1]) % 1000000007;
            }
        }
    }
    
    return graph[n][m] % 1000000007;
}