욕심쟁이 판다

#include<cstdio>
#include<queue>
#include<iostream>
#include<vector>
#include<utility>

using namespace std;

int a[501][501];
int d[501][501];

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

vector<int> r;

int n;

void cho(){
    for(int i = 1; i <= n; i++ )
    {
        for(int j = 1; j <= n; j++){
            d[i][j] = 0;
        }
    }
}

int bfs(int x, int y){
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    d[x][y] = 1;
    int solv = d[x][y];
    while(!q.empty()){
        int x = q.front().first; int y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i]; int ny = y+dy[i];
            if(nx > 0 && nx <= n && ny> 0 && ny <=n){
                if(d[nx][ny] == 0 && a[nx][ny] > a[x][y]){
                    q.push(make_pair(nx, ny));
                    d[nx][ny] = d[x][y] + 1;
                    if(solv < d[nx][ny]) solv = d[nx][ny];
                }
            }
        }
    }
    return solv;

}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    }
    int k = bfs(1,1);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            int temp =bfs(i,j);
            if(k < temp)
                k = temp;
            cho();
        }
        
    }
    printf("%d\n", k);
    return 0;

}

처음에 BFS로 한풀이.. 최대 단점은 모든 정점에서 시작해서 vector에 값을 푸쉬백해주기도하고

시간복잡도가 n^2승 이상으로 걸리지 않을까.. 값이 500 이넘어가면 훠어어얼씬 많을꺼같다는 생각도들고

하면서도 이게 브루트포스랑 크게 다른게뭐지? 라는생각도 들었던 풀이

당연히 시간초과나고 틀릴수밖에 없다

#include<cstdio>
#include<queue>
#include<iostream>
#include<vector>
#include<utility>

using namespace std;

int a[501][501];
int d[501][501];

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


int mx = 0;
int n;

void dfs(int x, int y) {
	int nx, ny;
	int result = 0;
	for (int i = 0; i < 4; i++) {
		nx = x + dx[i];
		ny = y + dy[i];
		if (nx <= n && nx > 0 && ny <= n && ny > 0) {
			if (a[nx][ny] < a[x][y]) {
				if (d[nx][ny] == 0)
					dfs(nx, ny);
				if (result < d[nx][ny])
					result = d[nx][ny];
			}
		}
	}

	d[x][y] = (result + 1);


	if (mx < d[x][y])
		mx = d[x][y];


}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			scanf("%d", &a[i][j]);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (d[i][j] == 0)
				dfs(i, j);
		}
	}

	printf("%d\n", mx);
	return 0;

}

DFS로 한풀이, 입력 제외하고 함수 진행하면서 시간단축을 좀많이한듯.. DFS랑 DP를 잘섞어놓은 문제같다.

나중에 한번 더 볼 필요가있는거같다.

재미있던 DP문제