SWEA-1949 등산로 조성

DFS로 해결했다. 일단 한번 n*n씩 탐색을 하면서 등산로의 봉우리값을 찾았고 다시 탐색을 하면서 봉우리값과 같으면 벡터에 push해주었다.

입력받은 칸을 복사한 뒤에 해당 벡터의 봉우리에 해당하지 않는다면 1부터 깊이만큼 빼가면서 탐색을 하였고 그 길이를 ans라는 변수에 저장하게 해서 결국 ans에는 최댓값이 저장되도록 하였다.

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

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

vector <pair<int, int> > v;
int ans, n, deep, maximum;
int map[8][8];
bool visit[8][8];

void dfs(int x, int y, int l, int arr[8][8]){
	if(ans<l)	ans=l;
	
	visit[x][y]=true;
	
	for(int i=0; i<4; i++){
		int nx=x+dx[i];
		int ny=y+dy[i];
		
		if(nx>=0&&ny>=0&&nx<n&&ny<n){
			if(visit[nx][ny]==false&&arr[nx][ny]<arr[x][y]){
				dfs(nx, ny, l+1, arr);
			}
		}
	}
	visit[x][y]=false;
}

int main(){
	int T;
	cin>>T;
	for(int test_case=1; test_case<=T; test_case++){
		ans=0;
		maximum=0;
		
		memset(visit, false, sizeof(visit));
		memset(map, 0, sizeof(map));
		v.clear();
		
		cin>>n>>deep;
		int status=0;
		int num;
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				cin>>map[i][j];
				if(i==0&&j==0)	num=map[i][j];
				else if(status==0){
					if(num!=map[i][j])	status=1;
				}
				if(map[i][j]>maximum)	maximum=map[i][j];
			}
		}
		
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(map[i][j]==maximum)	v.push_back(make_pair(i, j));
			}
		}
		
		if(status==0)	ans=2;
		
		else{
			for(int k=0; k<v.size(); k++){
				int x=v[k].first;
				int y=v[k].second;
				int amap[8][8];
				
				for(int i=0; i<n; i++){
					for(int j=0; j<n; j++)	amap[i][j]=map[i][j];
				}
				
				for(int i=0; i<n; i++){
					for(int j=0; j<n; j++){
						if(i==x&&j==y)	continue;
						
						for(int t=1; t<=deep; t++){
							amap[i][j]=amap[i][j]-t;
							dfs(x, y, 1, amap);
							amap[i][j]=amap[i][j]+t;
						}
					}
				}
			}
		}
		cout<<"#"<<test_case<<" "<<ans<<'\n';
	}
	return 0;
}