[백준][C++] 1520: 내리막 길

 

 

 

 

 

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

1520번: 내리막 길

 

 

 

 

---

- 문제

 

  2차원 배열이 있고, 상하좌우로 숫자가 작은 곳으로만 움직일 수 있다고 할 때 가장 우측하단에 도착할 수 있는 경우의 수를 구하는 문제다.

 

 

---

- 해설

1. (틀린 방법)

 

일반적인 dfs 방법으로 하나의 점에서 상하좌우를 확인하고 해당 조건에 맞으면 가장 우측하단에 있는 지점에 도착하는 경우의 수를 구하는 방법을 생각해봤다.

 

- 이동이 중복되는 경우도 있고, 경우의 수가 너무 많아서 시간초과가 남

 

 

2. (맞은 방법)

 

dfs(깊이우선탐색)이랑 dp(동적계획)을 같이 사용해보았다.

 

1) dp 배열은 -1로 초기화한다.(어느 지점에서 정답으로 가는 방법이 0가지 방법일 경우에 0이 겹칠 수 있으므로 -1이든 -1021이든 초기화)

 

2) 이미 dp가 저장된 곳이면 바로 반환하고 가장 우측하단의 경우에만 1을 반환한다.

 

3) 이러면 (0,0)에서 move 함수를 시작했어도 채워지는 dp배열은 가장 우측하단부터 채워질 것 같다.

 

 

 

---

- 풀이

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

int M, N, answer = 0;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int board[500][500];

void move(int m, int n){
    int newM, newN;
    if(M == m + 1 && N == n + 1){
        answer++;
    }
    for(int i = 0; i < 4; i++){
        newM = m + dx[i], newN = n + dy[i];
        if(newM >= 0 || newM < M || newN >= 0 || newN < N){
            if(board[m][n] > board[newM][newN]){
                move(newM,newN);    
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> M >> N;
    
    for(int i = 0; i < M; i++){
        for(int j = 0;j < N; j++){
            cin >> board[i][j];
        }
    }
    move(0,0);
    cout << answer;

    return 0;
}

 

 

#include <iostream>
using namespace std;

int M, N, answer;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int board[501][501];
int dp[501][501];  

int move(int m, int n){
    if(M == m + 1 && N == n + 1){
        return 1;               // 도착했으니 1을 더해주기
    }
    if(dp[m][n] != -1){
        return dp[m][n];        // 이미 도착했던 곳이면 그대로 반환
    }
    dp[m][n] = 0;
    for(int i = 0; i < 4; i++){
        int newM = m + dx[i];
        int newN = n + dy[i];
        if(newM >= 0 && newM < M && newN >= 0 && newN < N){
            if(board[m][n] > board[newM][newN]){
                dp[m][n] = dp[m][n] + move(newM,newN);
            }       // [M][N]부터 역으로 숫자를 세기면서 옴
        }
    }
    return dp[m][n];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> M >> N;
    
    for(int i = 0; i < M; i++){
        for(int j = 0;j < N; j++){
            cin >> board[i][j];
            dp[i][j] = -1;              // visited 대신에 -1, 0으로 해놓으면 해당 위치에 접할 수 없는 경우랑 겹침
        }
    }
    answer = move(0,0);
    cout << answer;
    

    return 0;
}

 

 

---

- 새롭게 알게 된 점