백준 1937 / C++ / dp

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

이 문제는전형 적인 dp문제이다 점화식만 세우면 문제되는 부분은 없었다 점화식은 dfs랑 비슷하게 생각하면되지만 
이문제의 핵심은 현재 칸에 왔을 때 내가 갈 수 있는 칸이 더많은 칸으로 가는거를 골라야한다 .

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
int arr[501][501] = { 0, };
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>> inputData;
int n;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int dp[501][501];
bool canGo(int x, int y) {
	if (x >= 1 && x <= n && y >= 1 && y <= n) {
		return true;
	}
	return false;
}
int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
			inputData.push({ arr[i][j],{i,j} });
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = 1;
		}
	}
	while (!inputData.empty()) {
		int curCost = inputData.top().first;
		int curX = inputData.top().second.first;
		int curY = inputData.top().second.second;
		inputData.pop();
		for (int i = 0; i < 4; i++) {
			int nextX = curX + dx[i];
			int nextY = curY + dy[i];
			
			if (canGo(nextX, nextY) && curCost < arr[nextX][nextY]) {
				dp[curX][curY] = max(dp[nextX][nextY] + 1, dp[curX][curY]);
			}
		}
	}

	int ans = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ans = max(ans, dp[i][j]);
		}
	}
	cout << ans;
}