[BOJ] 1937 : 욕심쟁이 판다

문제 링크

1937번: 욕심쟁이 판다 (acmicpc.net)

 

풀이

문제를 보면 일단 DFS문제라는 것을 알 수 있다.

시작점에서 상하좌우 중 범위를 벗어나지 않으면서 현재 지점보다 값이 크면 그 지점을 방문한다.

그렇게 해서 더 이상 이동할 수 없을때 까지 도달했을 때 그 깊이 중 가장 큰 값을 찾는 문제이다.

그런데 모든 점에서부터 출발해서 최대값을 찾으면 될까?? 당연히 아니다. 그렇게 하게되면 이미 방문했던 지점을 시작점으로 같은 경로를 재탐색 하게되는 경우가 발생하기 때문에 시간초과가 난다.

그럼 어떻게 해야할까? DP를 이용해서 재방문을 하지 않도록 해야한다.

예제를 보자

4
14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8

(1,1)을 출발점으로 했을 때 주변에 자신(14)보다 큰 값이 없으므로 더 이상 이동이 불가하다. 

따라서 DP[1][1] = 1

다음으로 9 ( 0, 1 )를 출발점으로 살펴보자 9->11->15의 경로로 이동했을 때 가장 많은 칸을 이동하게 된다.

이 탐색으로 한 번에 3개 지점의 최대 이동 칸 수를 알 수 있다.

9에서는 최대 2회 이동 할 수 있고, 11에서는 최대 1회 이동 할 수 있고, 15에서는 이동할 수 없다는 것을 의미한다.

나의 방법은 재귀를 이용해서 갈 수 있는 최대지점 까지 간 후에 15의 좌표인 DP[2][1] 에 1을 할당하고 함수를 빠져나가면서 15의 이전방문 지점인 11의 좌표가 (1,1)이므로 DP[1][1] = DP[2][1] + 1 을 할당해주고 또다시 함수를 빠져나가면서 11의 이전 지점 9의 좌표 DP[0][1] = DP[1][1] + 1 = (2 + 1)의 값을 할당해주었다. 이는 0,1에서 출발하면 최대 3칸 방문할 수 있다는 뜻이다.

그리고 DFS로 탐색하는 도중 이미 방문했던 지점이라면 DP배열에 값이 들어있을 것이다. 그럼 그 지점부터 갈 수 있는 횟수는 이미 알고있으므로 그 만큼 더해준 후 함수를 종료한다.

예를 들어 다른 출발점으로부터 경로를 탐색하다가 아까 방문한 11의 좌표 (1,1)에 도달했다고 하자 그럼 DP[1][1]에는 2가 저장되어 있을 것이고 이것으로 여기서는 최대 1회 더 이동할 수 있다는 것을 알아냈으니까 탐색은 그만해도 된다.

그럼 11 방문 이전좌표를 (y,x)라고 하면 DP[y][x] = DP[1][1] + 1이다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 500 + 5;
int DP[MAX_N][MAX_N];
int Forest[MAX_N][MAX_N];
int N;
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
int Max = 1;
bool is_ok(int y, int x, int num) {
    if (y < 0 || y > N || x <0 || x > N || num >= Forest[y][x])
        return false;
    return true;
}
 
void dfs(pair<int, int> before, pair<int, int> now) {
    int tree = Forest[now.first][now.second];
    bool chk = false;
    if (DP[now.first][now.second] != -1) {
        DP[before.first][before.second] = max(DP[before.first][before.second],
            DP[now.first][now.second] + 1);
        Max = max(Max, DP[before.first][before.second]);
        return;
    }
    for (int i = 0; i < 4; i++) {
        int next_y = now.first + dy[i];
        int next_x = now.second + dx[i];
        if (is_ok(next_y, next_x, tree)) {
            chk = true;
            dfs(now, { next_y, next_x });
        }
    }
    if (!chk) {
        DP[now.first][now.second] = 1;
        if (now != before) {
            DP[before.first][before.second] = max(DP[before.first][before.second],
                DP[now.first][now.second] + 1);
            Max = max(Max, DP[before.first][before.second]);
        }
        return;
    }
    if (now == before)
        return;
    DP[before.first][before.second] = max(DP[before.first][before.second],
        DP[now.first][now.second] + 1);
    Max = max(Max, DP[before.first][before.second]);
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            DP[i][j] = -1;
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> Forest[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (DP[i][j] == -1) {
                dfs({ i,j }, { i,j });
            }
        }
    }
    cout << Max << "\n";
    return 0;
}

이렇게 하면 중복을 피해 모든 지점을 탐색할 수 있다.