BOJ 1937 - 욕심쟁이 판다

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

 

처음에 풀때 단순하게 dfs 를 매 좌표마다 돌면서, 가장 큰 일수를 찾아내어, 답을 찾으려했지만 시간초과로 처리됬다.

#include <algorithm>
#include <iostream>
 
#define MAX 501
 
using namespace std;
 
int n, answer;
int adj[MAX][MAX];
bool visited[MAX][MAX];
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
int max_day;
 
void dfs(int r, int c, int day) {
    visited[r][c] = true;
    
    for (int i = 0; i < 4; ++i) {
        int ny = r + dy[i], nx = c + dx[i];
        if (ny < 0 || ny >= n || nx < 0 || nx >= n || visited[ny][nx]) continue;
        if (!visited[ny][nx] && adj[ny][nx] > adj[r][c]) {
            visited[ny][nx] = true;
            dfs(ny, nx, day + 1);
            visited[ny][nx] = false;
        }
    }
    
    max_day = max(max_day, day);
    visited[r][c] = false;
    return;
} 
 
void solve() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            max_day = 0;
            dfs(i, j, 1);
            answer = max(answer, max_day);
        }
    }
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> adj[i][j];
            
    solve();
    
    cout << answer;
    
    return 0;
}

 

위 코드에선 만약 dfs 를 수행할때 어떤 좌표에서 최악의 경우 모든 좌표들을 다 돌 수도 있다.

그래서 O(N^3) 가 되어서 시간 초과가 나는 것 같다.

 

dfs 로 탐색을 하는 것은 동일하게 하되, 메모이제이션을 위한 배열을 만들고 DP 방식으로 풀어야 시간 초과를 막을 수 있다.

DP[i][j] : 좌표 (i, j) 에서 가장 먼 길이의 값 (이 좌표에서 가장 오래 생존하는 일 수) 를 의미한다.

 

 

- c++

#include <algorithm>
#include <iostream>
 
#define MAX 500
 
using namespace std;
 
int n, answer;
int adj[MAX][MAX], days[MAX][MAX];
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
 
int dfs(int r, int c) {
    if (days[r][c]) 
        return days[r][c];
    
    days[r][c] = 1;
    
    for (int i = 0; i < 4; ++i) {
        int ny = r + dy[i], nx = c + dx[i];
        if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
        if (adj[ny][nx] > adj[r][c]) 
            days[r][c] = max(days[r][c], dfs(ny, nx) + 1);
    }
    
    return days[r][c];
} 
 
void solve() {
    for (int i = 0; i < n; ++i) 
        for (int j = 0; j < n; ++j) 
            answer = max(answer, dfs(i, j));
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n;
    for (int i = 0; i < n; ++i) 
        for (int j = 0; j < n; ++j) 
            cin >> adj[i][j];
            
    solve();
    
    cout << answer;
    
    return 0;
}