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

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

1520번: 내리막 길

풀이

1. 내리막길로만 이동하여 M, N 에 도달하는 경로의 수를 찾는 문제이다.

2. 단순하게 DFS 돌려봤으나 역시나 시간초과로 실패했다.

3. DFS + DP 방법과 우선순위 큐를 사용한 BFS 알고리즘으로 문제를 해결할 수 있다.

 

알고리즘: DFS + DP

1. dp[row][col] 에 저장 할 값은 M, N 에 도달하는 경로의 가지 수 이다.

2. dp[row][col] 을 -1로 초기화 하는데, 이때 -1이란 아직 특정 점에서 탐색을 시작하지 않았음을 뜻한다 (경로의 개수가 0인 점과 차이를 두기 위함).

3. DFS 재귀함수의 기저 조건은 row == M && col == N 일 때 1을 리턴하고 (도착), 또는 dp[row][col]의 값이 -1이 아니라면  dp 값을 리턴한다 (= 해당 점에서 타겟 점까지 가는 경로의 수를 알고 있음).

#include <iostream>
#include <vector>

using namespace std;
 
vector<vector<int>> map(502, vector<int> (501, 0));
vector<vector<int>> dp(502, vector<int> (501, -1));
int M, N, res;
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, -1, 1};
 
int DFS(int row, int col)
{
    if (row == M && col == N) return 1;
    if (dp[row][col] != -1) return dp[row][col];
 
    dp[row][col] = 0;
    for (int i = 0; i < 4; i++)
    {
        int nr = row + dr[i];
        int nc = col + dc[i];

        if ( nr < 1 || nr > M || nc < 1 || nc > N) continue;
        
        if (map[nr][nc] < map[row][col])
        {
            dp[row][col] += DFS(nr, nc);
        }
        
    }

    return dp[row][col];
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    // freopen("1520.txt", "r", stdin);
    cin >> M >> N; 
    for (int i=1; i<=M; i++) {
        for (int j=1; j<=N; j++) {
            cin >> map[i][j];
        }
    }

    cout << DFS(1, 1) << endl;

    return 0;
}

알고리즘 : 우선순위 큐 BFS

DAG 로 문제를 나타낼 수 있기 때문에 우선순위 큐 BFS로 풀 수 있다고 한다.

1. 우선순위 큐를 사용해서, 맵의 값이 큰 것을 우선으로 탐색할 수 있도록 한다.

2. visited 벡터에는 시작 점에서 해당 점까지 경로의 가짓수를 저장한다.

3. 우선순위 큐에 따라서, 순위가 낮은 위치는 나중에 나오게 되고 먼저 업데이트 한 위치를 다시 업데이트 할 수 있다(DAG를 생각해보자). 이때, 이미 방문한 점이라면 큐에는 다시 넣지 않는다 (= 그 점으로 오는 경로 수만 visited에 업데이트).

 

리뷰

요새 우선순위 큐를 사용한 그래프 문제를 자주 보다 보니 우선순위 큐로 푸는게 좀 더 자연스러운 것 같다... 

#include <iostream>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

// int map[501][501];
vector<vector<int>> map(501, vector<int> (501, 0));
vector<vector<int>> visited(501, vector<int> (501, 0));
int M, N, res;
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, -1, 1};

struct Data{
    int row, col, d;
    Data(int a, int b, int c) {
        row = a;
        col = b;
        d = c;
    }

    bool operator<(const Data& k) const {
        return d < k.d;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    // freopen("1520.txt", "r", stdin);
    
    cin >> M >> N; 
    for (int i=1; i<=M; i++) {
        for (int j=1; j<=N; j++) {
            cin >> map[i][j];
        }
    }

    priority_queue<Data> pq;
    pq.push(Data(1, 1, map[1][1]));
    visited[1][1] = 1;
    
    while (!pq.empty()) {
        Data v = pq.top();
        pq.pop();

        for (int i=0; i<4; i++) {
            int nr = v.row + dr[i];
            int nc = v.col + dc[i];

            if ( nr < 1 || nr > M || nc < 1 || nc > N) continue;

            if (map[nr][nc] < map[v.row][v.col]) {
                if (visited[nr][nc] == 0) {
                    pq.push(Data(nr, nc, map[nr][nc]));
                }
                visited[nr][nc] += visited[v.row][v.col];
            }
        }
    }

    //for (int i = 1; i<=M; i++) {
    //    for (int j=1; j<=N; j++) {
    //        cout << visited[i][j] << " ";
    //    }
    //    cout << endl;
    // }
    cout << visited[M][N] << endl;
    return 0;
}