백준, BOJ, 1937번, 욕심쟁이 판다 : C++ [CPP] ***

DFS + DP 문제다.

DFS를 어떻게 설계해야할까?

가 문제다.

 

 

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

 

---

 

#맞는 풀이

#include <iostream>
#include <algorithm>


#define X first
#define Y second

using namespace std;

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

int map[500][500];
int dp[500][500];

int N;


int ans;

//좌표
int dfs(int x, int y) {
    
    //만약 저장되어있지 않으면
    if(dp[x][y] == 0){
        dp[x][y] = 1; // 우선 해당 노드에서 1일 살 수 있음( + 방문체크와 같음)
        int cnt = 0; // 몇개나 다른 노드를 더 갈 수 있는지(DFS로)
        for (int dir = 0; dir < 4; dir++){
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (map[nx][ny] <= map[x][y]) continue;//방문체크를 안해줘도 되는이유 (여기서 역으로 못가는 조건이 걸러짐)
            cnt = max(cnt, dfs(nx,ny)); // 현재노드에서 DFS로 간 것 중에서 가장 큰 값(오래 살아남은 값)
        }
        dp[x][y] += cnt; // 해당 값을 현재 dp에 더함.
        
    }
    
    
    //저장되어 있거나, 계산 후에 dp의 값을 반환
    //가장 끝까지 가면 해당 노드는 1임. Bottom-Up 방식
    //그 전의 노드들은 이전 노드에서 1일 살고 끝노드로 가면 2가됨.
    //그 전 노드에서 1일 살고 끝노드까지가면 3이됨...
    //처음 노드에서 끝 노드까지 가면 k일 됨
    return dp[x][y];
}

int main() {
    cin >> N;

    //입력받기
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }

    //모든 지역에 대해서 조사
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            ans = max(ans,dfs(i, j)); //모든 노드에서 조사해본 결과의 최댓값

        }
    }

    cout << ans;

}

 

 

DFS를 진행하면서.. cnt를 갱신한다.

for문으로 4방향을 조사해서

한칸이라도 DFS로 갈 수 있으면 업데이트하면서 진행하고

 

마지막까지 도착해서 시작 노드의 값을 업데이트한다.

그리고 해당 시작노드의 값을 반환한다.

 

이렇게 DP와 탐색은 정말 많이 어울리는데

시간초과가 날 때 생각해볼만한 문제다.

 

해당 경로에 방향성이 있거나 해당 노드에서 갈 곳이 뻔하다는 것은

한 번 계산하면 중복해서 할 필요 없다는 이야기도 된다.

잘 생각해보자