1520

백준 1520번

Link: 1520번: 내리막 길

---

문제 설명

평범한 길찾는문제일줄 알고 우선 BFS부터 냅다 써서 풀었다.

분명 틀린 답은 아니다. 그런데 문제의 의도는 BFS 대신 DFS를 사용하여 메모리를 절약하고, DFS에 DP를 적용하여 시간을 절약하는 것이 의도였다.

DFS에 DP를 접목시키는 문제는 처음 보는것 같다.

그 느린 DFS를 이렇게 보완할수도 있구나 하는 생각이 들었다.

이 문제를 풀면서 BFS와 DFS의 차이를 제대로 체감할 수 있었던 것 같다.

BFS는 시간 내에 해를 찾을 수 있지만, 큐를 사용하는 만큼 더 많은 메모리 공간을 사용한다는 점이 특징.

DFS는 메모리 공간은 절약할 수 있지만, 깊이가 깊어질수록 매우 많은 시간을 요구한다는 점이 특징이다.

이러한 DFS의 깊이에 따른 문제를 보완하는 방법으로 DP를 사용하는 문제였다.

둘을 어떻게 접목시킬지 방법이 안떠올라서 결국 답을 찾아보고서야 이해할 수 있었다.

우선 DP 배열을 전부 -1로 초기화하고 시작한다.

그 다음, DFS를 목적지부터 (0, 0)까지 가도록 거꾸로 실행한다.

DFS에 들어가면 우선 DP 배열부터 살펴보게 되는데, DP[startX][startY]가 -1이 아니라는 것은 이미 저장된 값이 있으며, 이는 이미 탐색해서 구한 값이 있음을 의미하므로 그대로 리턴한다.

만약 startX나 startY가 범위를 벗어나면 0을 리턴하고, (0, 0)에 도착하게 되면 1을 리턴한다.

이 3가지 조건문에 걸리지 않았다는 것은 아직 탐색하지 않은 곳임을 의미하므로 탐색을 진행한다.

가장 먼저 DP[startX][startY]를 0으로 설정한다.

그 다음은 통상 아는 DFS를 진행하는데, 내려가는 방향으로만 갈 수 있고 우리는 DFS를 거꾸로 진행하고 있으므로 map[nextX][nextY]가 map[startX][startY]보다 클 경우에만 DFS를 진행한다.

조금 다른점이 있다면 통상 아는 DFS였다면 DFS(nextX, nextY)만 부르고 끝났겠지만, 이 문제는 DP를 접목시켜야 하므로 DP[startX][startY]의 값에 DFS(nextX, nextY)를 더한 값을 설정한다.

이때 연쇄적으로 재귀함수를 돌다 더 갈수 없으면 DP[startX][startY]를 리턴하고, 리턴되는 값을 계속 더해주는 것이다.

같은 방법으로 4방향 모두 탐색하며 DFS를 완성한다.

풀이방법을 외워둬야 할 것 같은 문제다.

BFS와 DFS의 차이점, DFS와 DP의 연계를 모두 배울 수 있는 문제였다. 까먹을때쯤 꼭 다시풀어볼 문제.

---

BFS로 풀다 틀린 코드

//
// Created by Keith_Lee on 13/01/2019.
//

#include <iostream>
#include <queue>

using namespace std;

int N, M;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int map[501][501];

int BFS(int startX, int startY){
    int result = 0;
    queue<pair<int, int>> Queue;

    Queue.push(make_pair(startX, startY));

//    vector<pair<int, int>> visits;

    while(!Queue.empty()){
        int currentX = Queue.front().first;
        int currentY = Queue.front().second;
        Queue.pop();

//        visits.push_back(make_pair(currentX, currentY));

        if(currentX == N && currentY == M){
//            for(int i=0; i<visits.size(); i++){
//                cout << map[visits[i].first][visits[i].second] << ' ';
//            }
//            cout << '\n';
//            visits.clear();
            result++;
        }

        for(int i=0; i<4; i++){
            int nextX = currentX + dx[i];
            int nextY = currentY + dy[i];

            if(nextX > 0 && nextX <= N && nextY > 0 && nextY <= N){
                if(map[currentX][currentY] > map[nextX][nextY]){
                    Queue.push(make_pair(nextX, nextY));
                }
            }
        }
    }

    return result;
}

int main(){
    cin >> M >> N;

    for(int i=1; i<=M; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
        }
    }

    cout << BFS(1, 1) << '\n';

    return 0;
}

---

정답 코드

//
// Created by Keith_Lee on 13/01/2019.
//

#include <iostream>
#include <memory.h>

using namespace std;

int N, M;

int map[501][501];
int DP[501][501];

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int DFS(int startX, int startY){
    if(DP[startX][startY] != -1){
        return DP[startX][startY];
    }
    if(startX < 0 || startX >= N || startY < 0 || startY >= M){
        return 0;
    }
    if(startX == 0 && startY == 0){
        return 1;
    }

    DP[startX][startY] = 0;

    for(int i=0; i<4; i++){
        int nextX = startX + dx[i];
        int nextY = startY + dy[i];

        if(map[nextX][nextY] > map[startX][startY]){
            DP[startX][startY] += DFS(nextX, nextY);
        }
    }

    return DP[startX][startY];
}

int main(){
    cin >> N >> M;

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> map[i][j];
        }
    }
    memset(DP, -1, sizeof(DP));

    cout << DFS(N-1, M-1) << '\n';

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cout << DP[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

---