[BOJ] #1520 내리막길

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

1520번: 내리막 길

---

골드3 정도 난이도의 DFS + DP를 활용한 문제이다. 처음에는 BFS로 접근을 했다가 여러 경로를 모두 탐색해야 하기에 visited 배열을 사용할 수 없음을 깨닫고 DFS로 방향을 틀었다가 시간초과가 나서 DFS에 DP를 접목시킨 방법으로 풀었다... 상당히 험난한 과정을 거쳤다.

애초에 행렬의 최대 사이즈가 500x500인 250,000이고, 방향 4개를 전부 탐색해야 하는데다가 그것도 하나의 경로가 아닌 여러개의 경로를 모두 찾아내야 하기 때문에 "아! DP를 안쓰면 무조건 시간초과가 날수밖에 없겠구나!"를 좀 더 빨리 깨달았다면 그나마 일찍 방향성을 잡고 풀었을 것이다. DP로 해결하는 방식은 아직 미숙하여 그랬던 것 같다.

#include <iostream>

#define MAX 501

using namespace std;

int M,N;
int cnt;
int arr[MAX][MAX];

int Dx[4] = { -1, 1, 0, 0 };
int Dy[4] = { 0, 0, -1, 1 };

void DFS(int x, int y) {
    if (x == M-1 && y == N-1) {
        cnt++;
        return;
    }

    for (int i=0; i<4; i++) {
        int newX = x + Dx[i];
        int newY = y + Dy[i];

        if (newX<0 || newX>=M || newY<0 || newY>=N) continue;

        if (arr[x][y] > arr[newX][newY]) DFS(newX, newY);
    }
}

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

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

    DFS(0,0);

    cout << cnt << '\n';

    return 0;
}

다음 코드는 DP를 사용하지 않고 DFS만 사용하여 작성했던 코드이다. 물론 저렇게 해도 답 자체는 똑같이 나올테지만,,, 시간초과에서 걸리게 된다. 따라서 DFS 기반에 DP를 활용하여 풀어야한다.

 

DP (Dynamic Programming 동적계획법)는 메모리를 적절히 사용하여 시간복잡도를 비약적으로 단축시킬 수 있는 방법이다. 이미 계산된 결과를 별도의 메모리 공간에 저장하여 다시 계산하지 않도록 함으로써 연산 시간을 단축시킬 수 있다.  DP는 일반적으로 하향식(top-down) 또는 상향식(bottom-up)으로 구현한다. 이 문제에서는 DP의 메모이제이션 기법을 활용하여 시간복잡도를 줄일 수 있다. (하향식 접근)

우선, 이미 탐색한 경로를 저장하는 DP 배열을 만들어야 하는데, 필자는

dp[x][y] => (x,y)로 갈 수 있는 경로의 개수

로 놓고 풀었다.

void makeDPtable() {
    for (int i=0; i<M; i++) {
        for (int j=0; j<N; j++) {
            dp[i][j] = -1;
        }
    }
}

그리고 처음에 dp 배열은 -1로 전부 초기화를 해주어야 하는데, 그 이유는 -1의 경우 "아직 도달한 적이 없는 좌표"라는 의미이고, 0의 경우는 "해당 좌표에서는 목적지로 갈 수 없음"을 의미한다. 이 두 경우를 따로 구분해주어야 제대로 탐색이 가능하다.

 

int DFS(int x, int y) {
    if (x == M-1 && y == N-1) return 1;
    if (dp[x][y] != -1) return dp[x][y];

    dp[x][y] = 0;

    for (int i=0; i<4; i++) {
        int newX = x + Dx[i];
        int newY = y + Dy[i];

        if (newX<0 || newX>=M || newY<0 || newY>=N) continue;

        if (arr[x][y] > arr[newX][newY]) {
            dp[x][y] += DFS(newX, newY);
        }
    }

    return dp[x][y];
}

DFS 함수가 호출되면, 처음에 dp[0][0]은 -1로 초기화 되어있으므로 다음 시퀀스로 넘어간다. dp[0][0]은 0으로 초기화되고 상하좌우를 탐색한다. 본인보다 작은값이 있으면 그 위치에 대해 DFS 함수를 재귀호출한다. 이런식으로 계속해서 재귀호출을 반복하다가 목적지에 도달하면 1을 return 한다. 이 return 값은 해당 함수를 호출했던 그 때 당시의 dp[x][y]값에 더해지는데, 그러면서 재귀 프레임이 하나씩 없어지게 된다.그러다 다시 시작점으로 돌아오게 되면, 이전에 분기했던 경로 중 가능한 또다른 경로 (상하좌우를 탐색할때 작은값이 두개 이상 나올 경우. 일종의 분기점이라 보면 된다.)로 다시 재귀호출을 반복하며 목적지까지의 경로를 탐색하게 된다.

이런 식으로 큰 문제를 작은 문제로 나눠서 작은 문제들의 해를 재귀적으로 구하고, 이를 취합하여 큰 문제의 해를 구하는 게 DP의 하향식 접근법이다. 그리고 한 번 계산된 결과를 저장하기 위해 메모이제이션 기법을 이용한다. (이 문제에서는 현재 칸에서 목적지까지 도달하는 경로의 개수가 dp 테이블에 저장된다.)

이렇게 글로 써놓고 보니 무슨 소린지 참... 비슷한 문제들을 여럿 풀어보며 계속해서 감을 잡아가야 할듯 싶다.

#include <iostream>

#define MAX 501

using namespace std;

int M,N;
int arr[MAX][MAX];
int dp[MAX][MAX];

int Dx[4] = { -1, 1, 0, 0 };
int Dy[4] = { 0, 0, -1, 1 };

void makeDPtable() {
    for (int i=0; i<M; i++) {
        for (int j=0; j<N; j++) {
            dp[i][j] = -1;
        }
    }
}

int DFS(int x, int y) {
    if (x == M-1 && y == N-1) return 1;
    if (dp[x][y] != -1) return dp[x][y];

    dp[x][y] = 0;

    for (int i=0; i<4; i++) {
        int newX = x + Dx[i];
        int newY = y + Dy[i];

        if (newX<0 || newX>=M || newY<0 || newY>=N) continue;

        if (arr[x][y] > arr[newX][newY]) {
            dp[x][y] += DFS(newX, newY);
        }
    }

    return dp[x][y];
}

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

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

    makeDPtable();

    cout << DFS(0,0) << '\n';

    return 0;
}