백준, BOJ, 1520번, 내리막 길 : C++ [CPP]

어렵지 않지만 생각은 해야하는 문제다.

나는 그냥 되는대로 풀었다가 된통당했다.

 

 

 

https://www.acmicpc.net/problem/1520

 

---

 

시간이 충분해보이지만 500*500에 대해서 하나의 경로가 아니라 여러 개를 조사한다면 미친 짓이다.

왜냐면.. 시간이 오래걸리기 때문이다.

 

#처음 틀린 풀이

#include <iostream>

using namespace std;


//0으로 초기화된 배열 선언
int map[501][501];
int dp[501][501];

int row, col;

int main() {
    cin >> row >> col;

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            cin >> map[i][j];
        }
    }
    //최초의 출발은 1값을 가짐 시작
    dp[0][0] = 1;

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            int cur = map[i][j];
            //i,j의 할당으로 조작하는 것은 for문의 오류를 불러올 수 있음 
            //i,j를 이용해서 값만 만들었음.
            
            //기존의 노드 값에서 이전노드들에서 오는 값을 더한 값. DP문제임을 알 수 있음

            //하
            if (i + 1 < row && cur > map[i+1][j]) {
                dp[i+1][j] += dp[i][j];
            }
            //상
            if (i - 1 >= 0 && cur > map[i-1][j]) {
                dp[i-1][j] += dp[i][j];
            }
            //우
            if (j + 1 < col && cur > map[i][j+1]) {
                dp[i][j+1] += dp[i][j];
            }
            //좌
            if (j - 1 >= 0 && cur > map[i][j-1]) {
                dp[i][j-1] += dp[i][j];
            }

            
        }
    }

    cout << dp[row - 1][col - 1];
}

 

이 풀이는.. 무엇을 간과하였냐면 

같은 노드를 2번 이상 지나는 경로가 있지만 그것을 계산하지 못한다.

 

 

#두 번째 틀린 풀이

#include <iostream>
#include <stack>

#define X first
#define Y second

int nx[4] = {1,-1,0,0};
int ny[4] = {0,0,1,-1};

using namespace std;


//0으로 초기화된 배열 선언
int map[501][501];
int cnt;
int row, col;
stack <pair <int,int>> stk;

int dp[501][501];

int main() {

    cin >> row >> col;

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            cin >> map[i][j];
        }
    }



    stk.push({0,0});

    while (!stk.empty()) {
        auto cur = stk.top();
        stk.pop();
        int dx = cur.X;
        int dy = cur.Y;

        for (int dir = 0; dir < 4; dir++) {
            int x = dx + nx[dir];
            int y = dy + ny[dir];
            if (x < 0 || x >= row || y < 0 || y >= col) continue;
            //방문 처리 안해도 내리막길원리에 의해 다시 방문하지 않음
            if (map[dx][dy] > map[x][y]) {
                if (dp[x][y] != 0) {
                    cnt += 1;
                    break;
                }
                dp[x][y] += 1;
                if (x == row-1 && y == col-1) {
                    cnt += 1;
                    break;
                }
                 stk.push({x, y});
            }
        }
    }

    cout << cnt;



}

 

이것 또한 그랬다.

 

dfs 자체를 저장하는 방법을 찾아야만 했다.

0,0에서 가는 방법은 1,0 + 0,1 이 아닐까 하면서 생각했다.

 

#include <iostream>

using namespace std;


int nx[4] = {1,-1,0,0};
int ny[4] = {0,0,1,-1};

//0으로 초기화된 배열 선언
int map[501][501];
int dp[501][501];

int row, col;



//dfs를 이용(x,y에서 row-1,col-1까지 가는 방법) 큰 것을 재귀적으로 나눔.
int dfs(int x, int y){
    // 끝에 도착했다면 1을 반환
    if(x == row - 1 && y == col - 1){
        return 1;
    }
    //그렇지 않고 처음 방문했다면
    else if(dp[x][y] == -1){
        //0으로 처리해줌
        dp[x][y] = 0;
        for(int dir = 0; dir<4; dir++){
            int dx = x + nx[dir];
            int dy = y + ny[dir];
            if( 0<=dx && dx < row && 0<=dy && dy < col && map[x][y] > map[dx][dy]){
                dp[x][y] += dfs(dx,dy);
            }
            
        }
    }
    //이미 방문했다면 저장된 값을 반환 또는 연산 끝나고 값읇 반환

    return dp[x][y];
}

int main() {

    cin >> row >> col;

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            cin >> map[i][j];
            dp[i][j] = -1;
        }
    }



    cout << dfs(0,0);



}

 

맞았다.

 

내가 만든 dfs는

x,y 부터 row-1, col-1 까지 조건에 맞게 가는 함수이다.