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

문제 & 링크

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

풀이

1. 모든 점에서 시작하여 가능한 모든 이동 경로를 완전 탐색하는 것은 시간 초과가 발생한다. 따라서 dp와 메모이제이션을 사용해야 한다.

2. 각 점에는 해당 점에서 시작했을 때의 최대 이동 칸 수를 저장한다. 이를 위해 2차원 dp 배열을 사용한다.

3. 모든 점이 도착 지점이 될 수 있으므로, 최소 이동 칸 수는 1로 초기화한다.

4. 전체 점들을 값 기준으로 내림차순으로 정렬하여, 값이 큰 점부터 탐색한다. 큰 점부터 dp 배열의 값을 구해놓으면, 작은 점에서 큰 점으로 이동 경로가 확장될 때, 추가적인 탐색 없이 작은 점의 dp 배열의 값을 구할 수 있다.

5. 탐색 시 인접한 네 방향을 확인하여, 최대 이동 칸 수를 dp 배열의 값으로 저장한다.

6. dp 배열의 값 중 가장 큰 값을 구하면 문제를 해결할 수 있다.

코드

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

using namespace std;

int map[501][501];
int dp[501][501];
vector<pair<int, pair<int, int>>> v;

int dr[4] = { 1, 0, -1, 0 };
int dc[4] = { 0, 1, 0, -1 };

int main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);

    int N;
    cin >> N;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
            v.push_back({ map[i][j], {i, j} }); // 가장 큰 값부터 탐색하기 위해 벡터 사용
            dp[i][j] = 1; // 모든 점이 이동 경로의 도착 지점이 될 수 있음
        }
    }

    sort(v.begin(), v.end(), greater<>()); // 내림차순 정렬

    // 값이 큰 점부터 주변의 네 점을 탐색하여, 본인보다 큰 점이 있다면 경로를 늘림
    // 내림차순으로 수행하기에 본인보다 큰 점을 만났을 때, 해당 점의 값을 그대로 더하면 됨
    int ans = 0;
    for (int i = 0; i < v.size(); i++) {
        int r = v[i].second.first;
        int c = v[i].second.second;

        int max_value = dp[r][c]; // dp[r][c]에서 제일 많이 이동한 칸의 수를 저장
        for (int j = 0; j < 4; j++) {
            int nr = r + dr[j];
            int nc = c + dc[j];

            if (1 <= nr && nr <= N && 1 <= nc && nc <= N) {
                if (map[nr][nc] > map[r][c]) {
                    max_value = max(max_value, dp[r][c] + dp[nr][nc]);
                    
                }
            }
        }
        dp[r][c] = max_value;
        ans = max(ans, dp[r][c]); // 모든 점 중 제일 많이 이동한 칸의 수를 저장
    }

    cout << ans;
}