백준 1937번 : 욕심쟁이 판다

  사육되는 판다의 평균 수명이 30년이므로 이 판다를 위해서는 적어도 대나무가 잘 정렬된 100 * 100의 숲을 준비해야한다!

 

  전형적인 DFS/BFS로 보이지만 그렇게 풀면 시간초과가 나기 때문에 DP를 써야하는 문제이다. 사실 이쯤되면 DFS/BFS는 DP의 하위 개념이 아닌가 싶다.

 

  아무튼 여기서 사용한 livingDay(x, y)라는 함수는 이 판다가 (x, y)의 지점부터 시작할 때 몇 일 살 수 있는가를 return해주는 함수이다. day라는 2차원 배열을 참고해서

 

    이미 day[x][y]가 구해져있다면 그 값을 그냥 return

    구해져 있지 않다면 값을 1로 초기화를 한 후, 4방향에 대해서 livingDay를 구해서 제일 큰 값을 취한다.

 

  근데 의문을 가질 수 있는게 '이미 방문한 곳을 다시 방문했을 때, 더 긴 루트를 발견할 수 있지 않나?'인데 애초에 livingDay라는 함수의 정의가 그 위치에서의 제일 긴 루트이고 모든 좌표는 반드시 한 번은 livingDay 함수를 거칠 수 밖에 없어서 이미 방문된 곳은 제일 긴 루트의 길이를 보유하고 있게 된다.

 

#include <stdio.h>
#include <iostream>
 
using namespace std;

int n;
int forest[504][504];
int day[504][504];

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int livingDay(int x, int y)
{
    if(day[x][y] != 0) return day[x][y];
    
    day[x][y] = 1;
    for(int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(0 <= nx && nx < n && 0 <= ny && ny < n)
        {
            if(forest[nx][ny] > forest[x][y])
            {
                day[x][y] = max(day[x][y], livingDay(nx, ny) + 1);
            }
        }
    }
    
    return day[x][y];
}

int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            cin >> forest[i][j];
        }
    }
    
    int ans = 0;
    for(int i = 0; i< n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            ans = max(ans, livingDay(i, j));
        }
    }
    
    cout << ans;
 
    return 0;
}