[C++] 백준 1937 : 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

 

DFS + DP

 

모든 (i, j) 에 대해서,

DP값(구해진 값) 이 없으면 해당 (i, j)부터 DFS를 들어간다 (있으면 그거 씀)

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (visit[i][j] == 0) {
            ans = max(ans, dfs(i, j));
        }
        else ans = max(ans, visit[i][j]);
    }
}

 

DFS에서, 주위에 갈 곳이 없으면 1을 리턴한다 (재귀함수의 말단)

주위에 갈 곳이 있다면 탐색하고(DFS), 그 결과에 +1 한 값 중 max 값을 취한다

탐색하는 과정에서 구한 값(DP)가 있으면 그 결과를 가져온다

 

를 맨 처음에는 아래 코드처럼 썼는데

int dfs(int si, int sj) {
	//dp값 가져오는 부분
	if (visit[si][sj] != 0) {
		return visit[si][sj];
	}
	
	bool all_small = true;
	for (int k = 0; k < 4; k++) {
		int ni = si + didj[k][0];
		int nj = sj + didj[k][1];
		//inbound, 조건
		if (ni < 0 || ni >= N || nj < 0 || nj >= N || map[ni][nj] <= map[si][sj]) continue;
		all_small = false;
		visit[si][sj] = max(visit[si][sj], dfs(ni, nj) + 1);
	}
	//return값 있어야함에 주의
	if (all_small) {
		visit[si][sj] = 1;
		return 1;
	}
	else {
		return visit[si][sj];
	}
}

 

다시 보니까 굳이 all_small이 필요가 없어서 아래처럼 고쳤다

int dfs(int si, int sj) {
	if (visit[si][sj] != 0) {
		return visit[si][sj];
	}

	visit[si][sj] = 1;
	for (int k = 0; k < 4; k++) {
		int ni = si + didj[k][0];
		int nj = sj + didj[k][1];
		//inbound, 조건
		if (ni < 0 || ni >= N || nj < 0 || nj >= N || map[ni][nj] <= map[si][sj]) continue;
		visit[si][sj] = max(visit[si][sj], dfs(ni, nj) + 1);
	}
	return visit[si][sj];
}

 

visit(DP역할도 함)에 값을 쓰는 것과 DFS 함수 자체가 리턴 하는 것이 섞여서 약간 헷갈렸었는데

문제 다 풀고 나서 보니까 괜찮다 꼭 문제 풀 때는 뭔가 잘 정리가 안된다..

 

지금 의문점인거는 이 부분인데,

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (visit[i][j] == 0) {
            ans = max(ans, dfs(i, j));
        }
        else ans = max(ans, visit[i][j]);
    }
}

맨 첨에는 그냥 모든 (i, j) 쌍들에 대해서 DFS를 진행했었는데

생각해보니까 그렇게 해 줄 필요가 없어서 (한 번 수행하면 그게 마지막 결과이고 더 커질 일 없음)

저렇게 바꿔준건데

한 번 수행하면 그게 마지막 결과이고 더 커질 일 없음 -> 의 근거를 명확하게 말 못하겠어서 계속 생각중...