[백준] 1937 욕심쟁이 판다 🐼 DP

문제 :

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

 

분석 :

n x n 판다 집이 있으면 판다는 상하 좌우로 움직일 수 있고 현 위치에서 다음 날이 될때 이동하는데 이동하는 칸에 먹이가 더 많아야 움직일 수 있는 욕심쟁이 친구다. 그래서 최대로 살 수 (?) 있게 하는 날을 구하는 문제였다.

 

arr배열에 밥을 넣어주고 dp를 동시에 0으로 초기화 시켜준 뒤

dp 함수를 돌면서 최대로 살 수 있는 maxRice (maxLife 변수가 더 적절할듯)를 갱신 시켜준다. 

 

find_max_life 함수 내에서는 우선 하루는 살 수 있기 때문에 현 위치에 1을 넣어주고 상하좌우를 탐색하면서 

다음 위치의 먹을 것이 현 위치보다 많은지, 배열 범위를 벗어나진 않은지 check 한다

그리고 dp 자리에 다음 위치로 움직였을때 또 살 수 있다면 +1씩 더한 재귀를 호출해 값을 증가시킨 뒤 움직임이 끝나 재귀가 종료되면 for문도 종료되고 그 자리의 움직일 수 있는 값을 출력한다.

 

c++ 코드 :

//
//  1937_selfishPanda.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/04/30.
//

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;
int arr[501][501];
int N;
int dp[501][501];

int dx[] = { 0, 0, 1, -1 }; //up down left right
int dy[] = { 1, -1, 0, 0 };

int find_max_life(int i, int j){
    if(dp[i][j] > 0){
        return dp[i][j];
    }
    
    dp[i][j] = 1;
    for(int k = 0; k < 4; k++){
        int nextX = i + dx[k];
        int nextY = j + dy[k];
        //예외처리
        if(nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) continue;
        if(arr[i][j] >= arr[nextX][nextY]) continue;
        //기존 값과 다음 먹이 찾으러 움직였을때 중의 최대값
        dp[i][j] = max(dp[i][j], find_max_life(nextX, nextY) + 1);
    }
    
    return dp[i][j];
}

int main(){
    cin >> N;
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> arr[i][j];
            dp[i][j] = 0;
        }
    }
    
//input 확인용
//    for(int i = 0; i < N; i++){
//        for(int j = 0; j < N; j++){
//            cout << arr[i][j] << " ";
//        }
//        cout << '\n';
//    }
    
    int maxRice = 0;
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
           maxRice = max(maxRice, find_max_life(i, j));
        }
        cout << '\n';
    }
    
    cout << maxRice <<'\n';
    
  
    return 0;
}