[백준] 1937: 욕심쟁이 판다

DFS를 풀다가 잠깐 이거 중복되겠는데라고 생각이 들었으나 우선은 마저 DFS로 풀었다.

DFS에서 그냥 탐색이 아니라 상하좌우 중 한 가지 경로를 택해야 하므로 += operator가 아니라 max 값을 추출해야 한다.

역시나 바로 시간 초과가 발생하였다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
bool visited[501][501];
long long trees[501][501];
int n;

bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}
int dfs(int x, int y) {
    int max_moves = 0, moves;

    for(int k = 0;k < 4;k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if(inside(nx, ny) && !visited[nx][ny] && (trees[x][y] < trees[nx][ny])) {
            visited[nx][ny] = true;
            moves = dfs(nx ,ny);
            max_moves = max(max_moves, moves);
            visited[nx][ny] = false;
        }
    }
    return max_moves + 1;
}
int main() {
    int answer = 0, moves = 0;
    cin >> n;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            cin >> trees[i][j];
        }
    }

    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            visited[i][j] = true;
            moves = dfs(i, j);
            visited[i][j] = false;
            if(moves > answer) answer = moves;
        }
    }

    cout << answer << '\n';


}

 

그래서 아래와 같이 메모이제이션을 위해 dp[i][j]에 trees[i][j]부터 코스에서 이동할 수 있는 최대 칸의 수를 기록을 한다.

즉 이미 이전에 최대 칸의 수 탐색이 끝났다는 의미이므로 우선 DFS 호출 시에 DP의 최초 방문이 아니면 바로 DP 값을 리턴하도록 하였다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
bool visited[501][501];
long long trees[501][501];
// dp[i][j]: i에서 시작해서 얻을 수 있는 최대 이동할 수 있는 칸의 수
vector<vector<int>> dp(501, vector<int>(501, -1));
int n;

bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}


int dfs(int x, int y) {
    int max_moves = 0, moves;

    // Memoization
    // 최초 출발지는 달라도 x, y 시점 이후 최대 칸 이동수는 동일하기 때문
    if(dp[x][y] != -1) return dp[x][y];

    for(int k = 0;k < 4;k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if(inside(nx, ny) && !visited[nx][ny] && (trees[x][y] < trees[nx][ny])) {
            visited[nx][ny] = true;
            moves = dfs(nx ,ny);
            max_moves = max(max_moves, moves);
            visited[nx][ny] = false;
        }
    }

    // max 값 판별 이후 dp에도 기록
    dp[x][y] = max_moves + 1;
    return max_moves + 1;
}
int main() {
    int answer = 0, moves = 0;

    cin >> n;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            cin >> trees[i][j];
        }
    }

    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            visited[i][j] = true;
            moves = dfs(i, j);
            visited[i][j] = false;
            if(moves > answer) answer = moves;
        }
    }

    cout << answer << '\n';
}