[DFS, 난이도 중상] 백준 1937번 욕심쟁이 판다

 

알고리즘이 DP로 분류되어 있긴 하지만 DFS에 더 가깝다고 생각했고,

내 풀이법은 일반적인 DFS풀이와 전혀 다를 것이 없기 때문에 카테고리를 DFS로 했다.

이전값을 참고하여 현재 정보를 갱신한다는 점에선 동적계획법이기도한 문제이다.

 

https://kimcoder.tistory.com/48

[동적계획법, 난이도 중상] 백준 1520번 내리막 길

백준 1520번이 내리막길이라면, 이 문제는 오르막길이다.

판다는 자신이 있는 좌표보다 더 많은 대나무가 있는 좌표로만 이동하기 때문이다.

본인은 백준 1520번 문제에서 입력된 표를 경로벡터를 가지는 그래프로 바꾸었는데 이 문제도 이렇게 접근하였다.

 

DFS를 수행하기 전 main문에서, 현재 좌표의 인접한 동서남북 좌표를 탐색하여 더 많은 대나무가 있는 좌표를 경로벡터에 넣어가며 그래프를 완성시켰다.

자신의 인접 노드는 현재 위치보다 더 많은 대나무가 있는 좌표들만 있다는 것이다.

고로 DFS에서는 인접노드가 없을 경우(a[x][y].size()==0) 1을 리턴하도록 했고(팬더는 1일만에 사망)

인접노드가 있을 경우 그 노드부터 깊이 우선탐색을 수행해나가며 인접노드들의 DFS리턴값중 최댓값 + 1 이 d[x][y] 이 된다.

 

Input은 예제 입력값이고

Input아래에 있는 DFS가 d[i][j]의 요소들이다.

 

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
int map[501][501];
int d[501][501];
vector<pair<int,int> > a[501][501];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int n;
int maxi(int a, int b) {
	if (a > b) return a;
	else return b;
}
int dfs(int x, int y) {
	if (a[x][y].size() == 0) return 1;
	if (d[x][y] == -1) {
		d[x][y] = 0;
		for (int i = 0; i < a[x][y].size(); i++) {
			int x2 = a[x][y][i].first;
			int y2 = a[x][y][i].second;
			d[x][y] = maxi(d[x][y],dfs(x2, y2)+1);
		}
	}
	return d[x][y];
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < 4; k++) {
				if (i + dx[k] < 0 || j + dy[k] < 0 || i + dx[k] >= n || j + dy[k] >= n)	continue;
				if (map[i][j] < map[i + dx[k]][j + dy[k]]) {
					a[i][j].push_back(make_pair(i + dx[k], j + dy[k]));
				}
			}
		}
	}
	memset(d, -1, sizeof(d));
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (d[i][j] == -1) d[i][j] = dfs(i, j);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ans = maxi(ans, d[i][j]);
		}
	}
	cout << ans;
}

 

 

 

+ 2021.09.28 숏코딩

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int map[501][501];
int d[501][501];
int cnt[501][501];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int n,m,fx,fy,ans;

int dfs(int x, int y){
	d[x][y]=0;
	for(int k=0;k<4;k++){
		fx=x+dx[k];
		fy=y+dy[k];
		if(fx<0||fx>=n||fy<0||fy>=n) continue;
		if(map[fx][fy]>map[x][y]){
			cnt[x][y]++;
			if(d[fx][fy]>0) d[x][y]=max(d[x][y],d[fx][fy]+1);
			if(d[fx][fy]==-1) d[x][y]=max(d[x][y],dfs(fx,fy)+1);
		}
	}
	if(!cnt[x][y]) d[x][y]=1; //갈 수 있는 인접 구역이 없을 경우
	return d[x][y];
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	memset(d,-1,sizeof(d));
	cin>>n;
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>map[i][j];
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(d[i][j]==-1) dfs(i,j); 
			if(d[i][j]>ans)ans=d[i][j];
		}
	}
	cout << ans;
}