[백준] 1937번 욕심쟁이 판다 (= greedy panda) - 재우스 프로그래밍 (C 언어)

문제 링크 :www.acmicpc.net/problem/1937

#include <stdio.h>

#define DEBUG 0
#define MAX_FOREST_SIZE 500

typedef struct _node {
    int bamboo;    //입력 받은 대나무 양
    int day;    //현재 위치에서 판다가 살기 시작할 때 살 수 있는 최대 일수
} node;
node forest[MAX_FOREST_SIZE][MAX_FOREST_SIZE];

int n;    //대나무 숲의 크기
int result;    //판다가 최대한 살 수 있는 일수

void calculateDay(int, int);    //인자로 들어온 좌표에서 판다가 시작했을 때 살 수 있는 최대 일수를 저장하는 함수

int main(void)
{
    n = 0;
    result = 1;

    //대나무 숲의 입력값 받아서 저장
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &forest[i][j].bamboo);
            forest[i][j].day = 0;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!forest[i][j].day)    //(i, j) 위치의 day가 갱신되어 있지 않다면 갱신해주는 함수 실행
                calculateDay(i, j);
            if (forest[i][j].day > result)    //(i, j)위치의 day가 최대 일수라면 결과값 갱신
                result = forest[i][j].day;
        }
    }

    printf("%d\n", result);

    return 0;
}

void calculateDay(int x, int y)
{
    int nx = 0, ny = 0;        //판다가 이동할 다음 좌표 저장
    char newX[4] = {1, -1, 0, 0};
    char newY[4] = {0, 0, 1, -1};

    for (int i = 0; i < 4; i++) {
        nx = x + newX[i];
        ny = y + newY[i];

        if (nx < 0 || nx >= n || ny < 0 || ny >= n)        //숲 내부 좌표가 아니라면 건너뜀
            continue;

        if (forest[x][y].bamboo < forest[nx][ny].bamboo) {    //다음 좌표의 대나무 양이 현재 좌표의 대나무 양보다 많다면 이동
            if (!forest[nx][ny].day)    //이동한 다음 좌표의 day가 갱신되어 있지 않다면 갱신해주는 함수 실행
                calculateDay(nx, ny);
            if (forest[nx][ny].day) {    //이동한 다음 좌표의 day가 갱신되었다면 현재 좌표의 day 갱신
                if (forest[x][y].day < forest[nx][ny].day + 1)
                    forest[x][y].day = forest[nx][ny].day + 1;
            }
        }
    }
    if (!forest[x][y].day)    //만약 상하좌우 어디로도 이동하지 못해서 (x, y)의 day가 갱신되지 않았다면 현재 좌표에서만 살고 끝이므로 1 저장
        forest[x][y].day = 1;

    return;
}