[ 백준 1937 ] 욕심쟁이 판다 (C++)

백준의 욕심쟁이판다(1937) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 얼핏보면, BFS/DFS로 쉽게 풀 수 있는 문제 같지만, BFS/DFS로 풀게될 경우, 시간초과 때문에 통과를 받을 수 없는 문제이다.

   따라서, Dynamic Programming으로 풀어야 하는 문제이다.

   먼저 전체적인 문제 풀이부터 알아보도록 하자.

   본인은 DP[][] 라는 2차원 배열을 사용하였는데, DP[a][b] = c 의 의미는 "판다가 (a,b)에 있을 때 최대로 살 수 있는

   날수는 c일입니다" 를 의미한다.

   DFS처럼 재귀호출 + DP로 이 문제를 해결할 수 있다. 모든 좌표에서, DFS를 통해서 판다가 상하좌우 중 움직일 수 있는

   방향에 대해서 움직여가면서 재귀를 계속해서 호출한다. 이 때, 이미 방문한 좌표에 대해서는 더이상 방문하지 않는다.

   그렇다면 왜 더이상 방문하지 않는지에 대해서 알아보자.

   "방문한 좌표를 또 방문하더라도, 그 길로 가다보면 더 오래살 수 있는 길이 나올 수 있지 않으므로 방문해봐야 하지 않나?"

   라는 의문이 생길수도 있다. 그렇다면 그림을 보면서 이해해보도록 하자.

  

   이러한 그림이 있다고 생각해보자. (0,0)에 판다를 냅둔다면, 아마 (0, 0) → (0, 1) → (0, 2) → (1, 2) → (1, 1) 을 통해서 총 5일을

   살게 될 것이다. 밑에 소스코드를 보면 알겠지만, 이렇게 좌표마다 재귀가 호출되는 과정에서 위에서 말한 DP[][]배열의 값이

   설정되어 진다. DP[0][0] = 5 , DP[0][1] = 4, DP[0][2] = 3, DP[1][2] = 2, DP[1][1] = 1 이런식으로 !

   이후에, (1, 0) 지점을 방문했다고 생각해보자.

   (1, 0)에서 (0, 0)으로 북쪽으로 판다를 움직인다면 어떻게 될까 ?? (0,0)지점은 이미 '5'라는 값을 가지고 있기 때문에 방문을

   해봤자, 결과는 5라는 값이 나오게 될 것이다. 즉, 이미 값이 있는 좌표는 방문을 더 이상 할 필요가 없다는 것이다.

   따라서, 재귀를 호출하는 과정에서 DP[][]  에 값이 있는 좌표라면 그대로 해당좌표의 DP[][] 값을 return 해주면 된다.

   그게 아니라면, 해당 좌표를 1로 설정해주고 탐색을 진행하면 된다.

   해당 좌표를 1로 설정해 주는 것은, 어느 좌표든지 판다를 놓는 순간, 그 좌표에서 1일은 살 수 있기 때문이다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 500
using namespace std;
 
int N, Answer;
int MAP[MAX][MAX];
int DP[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Bigger(int A, int B) { return A > B ? A : B; }
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
int Move(int x, int y)
{
    if (DP[x][y] != 0) return DP[x][y];
    DP[x][y] = 1;
 
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx >= 0 && ny >= 0 && nx < N && ny < N)
        {
            if (MAP[x][y] < MAP[nx][ny])
            {
                DP[x][y] = Bigger(DP[x][y], Move(nx, ny) + 1);
            }
        }
    }
    return DP[x][y];
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            Answer = Bigger(Answer, Move(i, j));
        }
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}