[ 백준 1937 ] 욕심쟁이 판다 (C++)

[문제 풀이]

1. 판다가 있는 좌표에서 상, 하, 좌, 우 중 이동할 수 있는 칸을 선택

2. 판다가 이동할 수 있는 칸 중에서 이미 다녀온 곳이면 DFS함수를 통해 계산하지 않고 다녀오지 않은 곳이면 DFS 함수를 통해 계산

3. 판다가 있는 좌표에서 상, 하, 좌, 우로 이동할 수 있는 곳 중에서 최댓값을 저장하고 반환

4. 모든 좌표 중에서 최대값을 정답으로 출력

[코드]

• 판다가 있는 좌표에서 상, 하, 좌, 우 중 이동할 수 있는 칸을 선택

// ni, nj 판다가 있는 좌표
int nx = ni + dx[i];
int ny = nj + dy[i];

// 대나무 숲의 범위를 넘어가는지 체크
if(nx >= N || nx < 0 || ny >= N || ny < 0) continue;

// 옮길 지역이 현재 판다가 있는 지역보다 대나무가 많은지 체크
if(map[nx][ny][0] <= map[ni][nj][0]) continue;

• 판다가 이동할 수 있는 칸 중에서 이미 다녀온 곳이면 DFS함수를 통해 계산하지 않고 다녀오지 않은 곳이면 DFS 함수를 통해 계산

// max 값은 판다가 이동할 수 있는 좌표 중에서 최댓값
if(map[nx][ny][1] == -1){
    go = DFS(nx, ny, 1);
    if(go > max){
        max = go;
    }
}else{
    if(max < map[nx][ny][1]){
        max = map[nx][ny][1];
    }
}

• 판다가 있는 좌표에서 상, 하, 좌, 우로 이동할 수 있는 곳 중에서 최댓값을 저장하고 반환

return map[ni][nj][1] = cnt + max;

• 모든 좌표 중에서 최대값을 정답으로 출력

// 이미 다녀온 곳인지 체크
if(map[ni][nj][1] == -1){
    tmp = DFS(ni, nj, 1);
}else{
    tmp = map[ni][nj][1];
}

if(tmp > answer){
    answer = tmp;
}

[전체 코드]

#include <iostream>
using namespace std;
int N, tmp, map[500][500][2], answer = 0;
int dx[5] = {0, 0, -1, 0, 1};
int dy[5] = {0, -1, 0, 1, 0};
int DFS(int ni, int nj, int cnt){
    int max = 0, go;
    for(int i=1; i<=4; i++){
        int nx = ni + dx[i];
        int ny = nj + dy[i];
        if(nx >= N || nx < 0 || ny >= N || ny < 0) continue;
        if(map[nx][ny][0] <= map[ni][nj][0]) continue;
        if(map[nx][ny][1] == -1){
            go = DFS(nx, ny, 1);
            if(go > max){
                max = go;
            }
        }else{
            if(max < map[nx][ny][1]){
                max = map[nx][ny][1];
            }
        }
    }
    return map[ni][nj][1] = cnt + max;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>N;
    for(int ni=0; ni<N; ni++){
        for(int nj=0; nj<N; nj++){
            cin>>map[ni][nj][0];
            map[ni][nj][1] = -1;
        }
    }
    for(int ni=0; ni<N; ni++){
        for(int nj=0; nj<N; nj++){
            if(map[ni][nj][1] == -1){
                tmp = DFS(ni, nj, 1);
            }else{
                tmp = map[ni][nj][1];
            }
            if(tmp > answer){
                answer = tmp;
            }
        }
    }
    cout<<answer<<"\n";
}

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