[C++] 백준 온라인 저지 1937번 욕심쟁이 판다 풀이

판다가 대나무 숲에서 며칠동안 살 수 있는지 구하는 문제

 

---

문제

 

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

 

입력

첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에는 판다가 이동할 수 있는 칸의 수의 최댓값을 출력한다.

 

 

풀이

 

 처음엔 DFS로 풀려 했으나 입력 최대값이 500이라 일반적인 DFS만으로는 시간 초과가 날 것이 뻔해 보였고... 문제 아래쪽에 알고리즘 분류 보니까 다이나믹 프로그래밍도 포함되어 있길래 DFS + DP로 풀어야 하는구나 까지는 알았습니다. 그래서 DP도 추가해서 탐색을 했는데 DP 배열의 중복 계산 처리를 안 해줘서 그런지 36%에서 계속 시간 초과가 나더라고요... 그래서 구글링을 해 보니 제가 어디에서 잘못 적었는지 알게 되었습니다. 

 이 문제 풀이의 핵심은 DFS로 탐색하되(BFS는 주변 칸 먼저 탐색해서 비효율적) 메모이제이션을 이용해 이미 거리 계산을 한 곳이라면 더 방문할 필요가 없도록 코드를 짜는 것입니다. 제가 처음에 이걸 제대로 못 해서 500 짜리 입력을 통과하지 못 했습니다. 

 

 

 예제 입력을 보면 최대값이 4라는 것은 쉽게 알 수 있습니다. 그런데 가능한 경로를 계산해보면 한 가지 경로만이 아닌 여러 경로를 통해서 최대값 4를 얻을 수 있습니다.

 4 -> 5 -> 11 -> 15

 3 -> 6 -> 7 -> 15

 2 -> 5 -> 11 -> 15 등 15까지 도착하는 데 4칸이 걸리는 경로가 꼭 한 가지는 아닙니다. 그러면 15까지 가기 위한 경로들을 굳이 여러 번 탐색할 필요가 없습니다. DFS를 이용하면 어차피 가장 깊은 곳까지 탐색하게 되어 있고 DP 배열에 가장 깊은 경로를 기록했다면 그 이후로는 탐색을 해도 똑같은 결과를 얻을 것이기 때문이죠. 그렇기 때문에 DFS 함수를 재귀로 방문했을 때에 해당 위치의 메모이제이션 값이 0보다 크다면 이미 방문한 곳이니까 더 탐색할 필요 없이 해당 위치의 메모이제이션 값을 반환하면 됩니다. 만약 방문하지 않은 곳이라면 메모이제이션 값을 1로 바꿔준 다음에(판다가 맨 처음 방문한 곳도 포함하니까) DFS 탐색을 진행하면 됩니다. 

 

 

코드

 

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<vector<int>> dir;
int dfs(vector<vector<int>>& forest, vector<vector<int>>& DP, pair<int, int> cur)
{
    //0이 아니면 이미 탐색한 곳이니까 현재값 리턴 
    if (0 != DP[cur.first][cur.second])
        return DP[cur.first][cur.second];
    
    //0이면 탐색하지 않은 곳이니까 초기값 1로 세팅 
    DP[cur.first][cur.second] = 1;
    
    for (int i = 0; 4 > i; i++)
    {
        auto next = make_pair(cur.first + dir[i][0], cur.second + dir[i][1]);
        if (0 > next.first || N <= next.first || 0 > next.second || N <= next.second)
            continue;
        //다음 위치가 지금 위치보다 더 크다면 
        if (forest[cur.first][cur.second] < forest[next.first][next.second])
        {
            //메모이제이션을 하는데 dfs 탐색 값과 현위치 메모이제이션 값 중 큰 값을 저장한다. 
            DP[cur.first][cur.second] = max(dfs(forest, DP, next) + 1, DP[cur.first][cur.second]);
        }
    }
    
    //위 반복문이 끝나면 현재 위치에서 갈 수 있는 경로의 최대값을 리턴하게 될 것임 
    return DP[cur.first][cur.second];
}

int main()
{
    dir.push_back({1,0});
    dir.push_back({-1,0});
    dir.push_back({0,1});
    dir.push_back({0,-1});
    
    cin >> N;
    
    vector<vector<int>> forest(N, vector<int>(N, 0));
    for (int i = 0; N > i; i++)
        for (int j = 0; N > j; j++)
            cin >> forest[i][j];
    
    int answer = 0;
    vector<vector<int>> DP(N, vector<int>(N, 0));
    for (int i = 0; N > i; i++)
    {
        for (int j = 0; N > j; j++)
        {
            //정답을 최대값으로 갱신 
            answer = max(dfs(forest, DP, make_pair(i, j)), answer);
        }
    }
    
    cout << answer;
    
    return 0;
}

 

 이제 DFS/BFS까진 잘 짜는데 DP(특히 메모이제이션)에 아직 약해서 응용해야 하는 문제는 푸는 데 오래 걸리네요 ㅠ.ㅠ 그래도 완전 초창기에 비하면 많이 나아져서 그걸로 위안삼기...