BOJ - 1937 욕심쟁이 판다

1937번 욕심쟁이 판다

판다가 현재 위치하고 있는 곳의 대나무를 다 먹고 상하좌우로 이동을 한다. 이 때 이동할 곳의 대나무가 현재 있던 곳의 대나무보다 적다면 이동을 하지 않고 굶어 죽는다.

위의 상황에서 판다를 어딘가에 처음 위치 시켰을 때 판다가 가장 오래 살아있을 수 있는 기간을 구하는 문제이다.

문제 해결 전략

예를 들어 판다가 (1,1)->(1,2)->(2,2)로 이동을 했다고 생각해 보자.

(1,1)에서 출발 했을 때의 살아있는 기간은 3일이 된댜.

그리고 (1,2)에서 출발했을 때의 살아있는 기간은 2일이 된다.

만약 이전에 선택한 좌표에서의 이동 경로 중 현재 선택한 좌표가 있다면 현재 선택한 좌표는 무조건 이전 좌표의 날 수 보다 작을 것이니 따로 계산을 할 필요가 없다.

또한 새로 선택한 좌표에서 출발하는 경우 이동 경로 중 다른 좌표에서 출발할 때 거쳤던 곳을 한번 더 거친다면 그 때 저장된 값과 현재 누적된 값을 비교하여 더 큰 값을 저장해 준다.

즉, DP를 활용하여 저장된 값을 활용하는 것이다.

문제 해결 순서는 다음과 같다.

1. 대나무의 양을 내림차순으로 정렬한다.

2. 대나무의 양이 많은 곳부터 적은 곳으로 이동을 한다.

3. 이동 과정에서 이동할 곳에 저장되어 있는 기간 과 현재 기간 + 1 을 비교하여 더 큰 값을 저장해 준다.

4. 저장된 값 중 가장 큰 값을 구한다.

코드

 #include <iostream>
#include<vector>
#include<algorithm>

using namespace std;

int arr[501][501];
int visited[501][501];
int xpo[4] = {-1,1,0,0};
int ypo[4] = {0,0,-1,1};
vector<pair<int, pair<int,int>>> v;
int n;
int dp(){
    for(int i=0;i<v.size();i++)
    {
        int x = v[i].second.first;
        int y = v[i].second.second;

        for(int j=0;j<4;j++)
        {
            int nx = x + xpo[j];
            int ny = y + ypo[j];
            if(nx < 0 || nx >= n || ny < 0 || ny >= n)
                continue;

            if(arr[nx][ny] > arr[x][y])
            {
                if(visited[x][y] < visited[nx][ny] + 1)
                    visited[x][y] = visited[nx][ny] + 1;
            }
        }
        if(visited[x][y] == 0)
            visited[x][y] = 1;
    }

    int max = 0;
    for(int k=0;k<n;k++)
    {
        for(int j=0;j<n;j++)
        {
            if(visited[k][j] > max)
                max = visited[k][j];
        }
    }
    return max;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin >> arr[i][j];
            v.push_back(make_pair(-arr[i][j], make_pair(i,j)));
        }
    }

    sort(v.begin(), v.end());

    cout << dp();

    return 0;
}

출처 : https://www.acmicpc.net/problem/1937