[BOJ 1937] 욕심쟁이 판다(c++)

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

 

문제 개요

n × n 크기의 대나무 숲에서 판다가 이동할 수 있는 최대 칸 수를 구하는 문제입니다. 판다는 현재 위치보다 대나무가 더 많은 곳으로만 이동할 수 있습니다.

(1 ≤ n ≤ 500)

(1 ≤ 대나무 양 ≤ 1,000,000)

---

문제 풀이

DP를 활용하여 문제를 해결하였습니다. 대나무 양이 적은 곳부터 많은 곳 순서로 정렬을 하여 현재 칸을 방문할 때, 더 작은 값부터 최대 이동 칸 수를 DP에 저장하였습니다. 또한, 현재 위치보다 대나무가 적은 인접 칸의 DP값들을 이용해 빠르게 계산하였습니다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
int coord[502][502];
int dp[502][502];

class node {
public:
    int x, y, val;
    bool operator < (const node& other) const {
        return val < other.val;
    }
};

vector<node> v;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    
    // 입력 및 노드 저장
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> coord[i][j];
            v.push_back({ i, j, coord[i][j] });
        }
    }
    
    // 대나무 양 기준 오름차순 정렬
    sort(v.begin(), v.end());
    
    int res = 0;
    
    // 작은 값부터 DP 계산
    for (node cur : v) {
        dp[cur.x][cur.y] = 1;  // 현재 칸
        
        // 4방향 탐색
        for (int i = 0; i < 4; i++) {
            int tx = cur.x + dx[i];
            int ty = cur.y + dy[i];
            
            // 현재 칸보다 대나무가 적은 인접 칸에서 올 수 있음
            if (coord[cur.x][cur.y] > coord[tx][ty]) {
                dp[cur.x][cur.y] = max(dp[cur.x][cur.y], dp[tx][ty] + 1);
            }
        }
        
        res = max(res, dp[cur.x][cur.y]);
    }
    
    cout << res;
    return 0;
}