[C++] 백준 1937번 욕심쟁이 판다 풀이

문제

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

1937번: 욕심쟁이 판다

 

이 문제는 DFS나 BFS로 간단히 풀 수 있는 문제처럼 보인다. 하지만 기본적인 DFS나 BFS로 풀 경우 시간초과가 발생한다. 따라서 DFS와 DP를 결합한 메모이제이션 방식을 이용해야한다. 그렇다면 메모이제이션을 어떻게 사용해야할까?

 

예시

입력 배열

만약 (0,0)인 5에서 시작한다면 5, 6, 7, 8, 9, 15까지 탐색 가능하며 2차원인 DP배열은 다음과 같을 것이다.

DP 배열

5에서 시작하면 총 7번까지 탐색 가능하다. 만약 그렇다면 (1,0)인 3에서 탐색을 시작한다면 어떻게 될까? 3에서는 5방향으로 탐색한다면 5에서 시작한 것과 똑같이 탐색할 것이다. 5부터는 결과도 똑같을 것이다. 그렇다면 3은 5에 이미 탐색한 결과가 있을 경우 DP배열의 (0,0)에 1을 더해주기만 하면 탐색 가능한 최대값을 얻을 수 있을 것이다. 만약 그렇지 않고 5부터 다시 탐색한다면 같은 반복을 여러번할 것이다. 만약 3부터 탐색하고 (1,1)인 2부터 탐색한다면 같은 작업을 3번 반복하는 것이다. 엄청난 시간낭비가 발생한다. 그렇기 때문에 이미 계산한 결과가 있는 경우 탐색을 멈추고 그 결과값을 이용해야한다. 코드로 나타내면 다음과 같다.

#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

const int MN = 501;

int dp[MN][MN]; //DP 배열
int arr[MN][MN]; //입력 배열
bool visit[MN][MN]; //방문 배열
int N;
int di[4] = {1, 0, 0, -1}; //상하좌우 표시
int dj[4] = {0, 1, -1, 0};

int dfs(int i, int j) {
    if(visit[i][j]) return dp[i][j]; //만약 이미 계산한 결과값이 있는 경우 사용
    visit[i][j] = true; //방문 표시
    dp[i][j] = 1; //첫 방문인 경우 1로 초기화
    for(int d = 0; d < 4; d++) { //상하좌우를 탐색
        int ni = i + di[d];
        int nj = j + dj[d];
        if(ni >= 0 && ni < N && nj >= 0 && nj < N) { //배열 범위를 벗어나지 않는 조건
            if(arr[ni][nj] > arr[i][j]) //더 많은 대나무가 있는 곳으로
                dp[i][j] = max(dp[i][j],dfs(ni, nj) + 1); //탐색하고 최대값 갱신
        }
    }
    return dp[i][j]; //현 위치에서의 최대값 리턴
}

int main() {
    cin >> N;
    int ans = 1;
    for(int i = 0; i < N; i++) { //입력받기
        for(int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            ans = max(ans,dfs(i, j)); //각 위치에서 시작하여 최대값 갱신
        }
    }

    cout << ans; //최대값 출력
    return 0;
}

DFS와 DP를 이용하여 불필요한 재방문을 스킵하면 시간을 줄일 수 있다. 메모이제이션은 DP가 어떤 값을 기억하는지를 정확히 알고 이해해야지 사용할 수 있다. 카카오 코딩테스트에서도 가끔 메모이제이션을 사용하는 문제가 나오기 때문에 이런 문제를 많이 풀어보는 것이 중요하다.