[백준] 1937번 - 욕심쟁이 판다 (C언어) [Gold3]

input	output
4 14 9 12 10 1 11 5 4 7 15 2 13 6 3 16 8	4

해당 문제를 먼저 해석하면, n x n 크기의 대나무 숲은 2차원 배열로 정의한다. 판다는 대나무가 많은 곳으로 이동하기 때문에 판다가 이동하는 만큼 생존한다고 볼 수 있다. 판다가 생존 가능한 최대 일 수는 아래 표로 정리하였다.

 

해당 문제는 DFS와 동적 계획법을 사용한다면 해결가능한 문제이다. 만약, DFS만을 진행한다면 이미 탐색한 곳에 대해서 다시 탐색하는 의미없는 탐색을 진행하기 때문에 최대 깊이까지 탐색한 후 백트래킹을 통해 동적계획법의 값을 저장한다. 백트래킹시에 현재 값에 1을 더해준 값을 반환한다. 

 

전체 소스 코드는 아래와 같다.

#include <stdio.h>
#define max(X,Y) ((X) > (Y) ? (X) : (Y)) // max 정의
#pragma warning(disable:4996)

int n;
int bamboo[1001][1001]; // 대나무 좌표
int sum[1001][1001]; // 판다 생존 일수

int dx[] = { -1,1,0,0 }; // x 좌표
int dy[] = { 0,0,1,-1 }; // y 좌표

int dfs(int x, int y) { // dfs 와 동적 계획법 사용
    if (sum[x][y] != 0) 
        return sum[x][y];

    sum[x][y] = 1; // 초깃값 설정
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i]; 
        int ny = y + dy[i];
        

        if (ny < 0 || nx < 0 || nx >= n || ny >= n) // 범위를 벗어난 경우
            continue;
        if (bamboo[nx][ny] > bamboo[x][y]) { // 판다가 생존할 수 있는 일 수 갱신 
            sum[x][y] = max(sum[x][y], dfs(nx, ny) + 1 );
        }
    }
    return sum[x][y];
}


int main() {

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &bamboo[i][j]);
		}
	}

	int result = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            result = max(result, dfs(j, i)); // 최댓값 갱신
        }
    }

    printf("%d", result);

	return 0;
}

[동적계획법]

https://hongjw1938.tistory.com/47

알고리즘 - Dynamic Programming(동적 계획법)

 

[1937번]

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

1937번: 욕심쟁이 판다

 

[github]

https://github.com/MinWook6457

MinWook6457 - Overview