[C++] 백준 1937번: 욕심쟁이 판다

🔗 문제

1937번: 욕심쟁이 판다

1937번: 욕심쟁이 판다

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

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

입력

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

출력

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

 

🖍 풀이

문제 정리

• map[MAX][MAX] (MAX = 500)의 맵이 있다.
• map[x][y] < map[nextX][nextY] 조건일 때만 상하좌우 이동이 가능할 때 최대 이동 거리 구하기

 

평범하게 DFS를 하게 되면 시간 초과를 보게 된다.

DFS에서 visited (true → false)해줘도 시간초과다. 되추적하면서 재방문 표기를 풀면서 갔던 경로를 어쨌든 또 가기 때문이다. 그러지말고 DP에 그 정점이 도착점일 때의 최대 이동 거리를 저장해준다.

• DFS : 한 지점을 시작으로 하는 최대 이동 거리를 구한다.
• DP : 이미 방문한 곳이라면 DFS 탐색을 해본 경로다. 저장된 이전 거리와 현재 거리를 비교하여 갱신만 해준다.

 

💾  소스

#include <iostream>
#include <cmath>

const int MAX = 500 + 1;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

int N;
int map[MAX][MAX], DP[MAX][MAX] = {0, };

bool isValid(const int x, const int y)
{
    if(x<0 || y<0 || x>=N || y>=N)
        return false;
    return true;
}

int DFS(const int _x, const int _y)
{
    if(DP[_x][_y] != 0) // 이미 방문한 곳이면 시간 줄이기 위해서 컷
        return DP[_x][_y];

    DP[_x][_y] = 1;
    
    for(int d=0; d<4; ++d)
    {
        int x = _x + dx[d];
        int y = _y + dy[d];

        if(!isValid(x, y) || map[x][y] <= map[_x][_y])
            continue;
        
        // 이미 방문한 구역이 있네?
        if(DP[x][y] != 0)
        {
            // 전에 방문했던 길이랑 지금 방문하는 길이 중 뭐가 더 큰지만 체크
            DP[_x][_y] = std::max(DP[_x][_y], DP[x][y]+1);

            continue;
        }
	
        //방문하지 않은 구역만 DFS 진행 ~ 
        DP[_x][_y] = std::max(DP[_x][_y], DFS(x, y)+1);
    }

    return DP[_x][_y];
}

int main()
{
    std::cin >> N;
    
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<N; ++j)
            std::cin >> map[i][j];
    }
    
    int answer = 0;
    for(int i=0; i<N; ++i)
        for(int j=0; j<N; ++j)
            answer =  std::max(answer, DFS(i, j));

    std::cout << answer;
    
    return 0;
}