[백준 1937] 욕심쟁이 판다

문제 요약

• N*N 크기 배열의 대나무 숲에는 각 칸마다의 대나무 양이 적혀있다.
• 욕심쟁이 판다는 자신이 위치한 칸의 대나무를 다 먹어치우고 상하좌우 중 한 곳으로 이동하는 습성을 갖고 있다. 근데 웃기는 게 욕심쟁이라서 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-)
• 욕심쟁이 판다를 어느 위치에 놓는지, 어떤 방향으로 움직이는지가 판다의 생존 일수를 결정한다. 사육사는 해당 대나무 숲에서 판다가 가장 오래 생존할 수 있는 기간이 궁금하다.

아이디어

이틀 전에 푼 알파벳 문제와 거의 같은 로직을 활용해 풀었다.
DFS와 DP를 혼용하는 것이다. DP라고 해봤자 거창한 건 아니고 걍 해당 위치에서 가장 긴 PATH의 길이를 저장해놓는 것이다. 재귀적 DFS로 가장 긴 DEPTH를 반환함으로써 구현했다.

왜 DP를 써야할까? 어차피 재귀로 리턴 받는데..

이 문제 풀이의 핵심은 한 번 방문한 노드는 다시 탐색하지 않는 것이다. 이미 탐색한 tree는 자기 자신의 하부에 붙인다고 할 수 있다.
이로써 2차원 배열 DFS의 O(노드수+4노드수)를 유지할 수 있다.(다시 DFS로 탐색했다면 seed를 어케 잡느냐에 따라 탐색한 트리를 다시 돌아 비효율적이다.)
DFS 결과물을 DP 테이블에 저장을 함으로써 다시 탐색하지 않고 해당 결과물을 상부에 리턴한다. 여담으로 이게 가능한 이유는 DP테이블이 의미하는 것이 자기 자신을 SEED로 삼았을 때 갖는 하부 TREE의 PROPERTY이기 때문이다. 상부 TREE의 PROPERTY라면(루트로부터 얼마나 떨어져있는가) 새로 연결될 때마다 갱신 해줘야하기 때문에...

SEED 관련 팁

시드를 찾아낼 때 2차원 배열을 순서대로 돌면서 찾는 경우가 많은데, 이전 시드 다음위치부터 찾으면 이미 확정적으로 순회가 완료된 부분을 돌지 않아도 되서 더 빠르다. 시간 복잡도 상으론 큰 의미가 없겠지만.. 한 번 이 문제 때문에 시간 초과가 뜬 적이 있기에!

소스코드

#include<iostream>
#include<math.h>
#include<iomanip>
using namespace std;
int n;
int tab[500][500];//250000개의 노드
int dp_depth[500][500];//-1로 초기화
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
struct pos {
	int i, j;
};
bool inbox(int i, int j) {
	return i >= 0 && i < n&& j >= 0 && j < n;
}
int dfs(int mi, int mj) {//재귀를 통해 현재 위치에서 얼마나 깊게 갈 수 있는지를 저장
	if (dp_depth[mi][mj] != -1) {
		return dp_depth[mi][mj];
	}

	dp_depth[mi][mj] = 0;
	for (int k = 0; k < 4; k++) {
		pos c = pos{ mi + di[k],mj + dj[k] };
		if (inbox(c.i, c.j) && tab[c.i][c.j] > tab[mi][mj]) {
			dp_depth[mi][mj] = max(dp_depth[mi][mj], dfs(c.i, c.j) + 1);
		}
	}
	return dp_depth[mi][mj];
}
pos get_seed(pos past_seed) {
	for (int i = past_seed.i; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dp_depth[i][j] == -1) {
				return pos{ i,j };
			}
		}
	}
	return pos{ -1,-1 };
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> tab[i][j];
			dp_depth[i][j] = -1;
		}
	}

	pos seed = get_seed(pos{ 0,0 });
	while (seed.i != -1) {
		dfs(seed.i, seed.j);
		seed = get_seed(seed);
	}
	//집계
	int max_res = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			max_res = max(max_res, dp_depth[i][j]);
		}
	}
	cout << max_res+1;
}

버린 아이디어

BFS를 하면서 LEVEL을 적는 방법

어떤 SEED로부터 이어졌을 때 레벨이 몇인지를 함께 저장하는 것이다. 이렇게 하면 일치하는 SEED가 있다면 뺄셈을 통해 각 노드간의 거리를 알 수 있다.

포기한 이유 : 이미 탐색한 TREE와 접붙이기를 할 때 이미 탐색한 TREE를 돌면서 어떤 COMPONENT와 이어지는지를 APPEND 해줘야한다.(왜 APPEND냐면 TREE라고 표현 하긴 했지만 여러 노드를 부모로 가질 수 있기 때문에..)
그래야 상단 노드와 하단노드의 연결관계를 알 수 있다.