[백준][BOJ][C++][1937번] 욕심쟁이 판다(시간초과)

요번 문제는 해결을 하지 못하였고 시간초과가 발생하였습니다. 일단 코드를 공유하고 해결하면 다시 올리도록 하겠습니다.

문제

n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-)

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n*n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 오래 살려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력

첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

 

코드

#include<iostream>
#include<queue>
#include<algorithm>
#include<memory.h>
using namespace std;
 
struct info{
    int x;
    int y;
    int day;
};
 
int N;
int ans;
int map[502][502];
int visited[501][501];
int px[4] = { 0,1,0,-1 };
int py[4] = { 1,0,-1,0 };
int temp_ans;
queue<info>qq;
queue<info>q;
 
void printt() {
    for (int y = 1; y <= N; y++) {
        for (int x = 1; x <= N; x++) {
            cout << visited[y][x] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
 
//void bfs(int x, int y) {  //시간초과
//    while (!qq.empty()) {
//        visited[qq.front().y][qq.front().x] = false;
//        qq.pop();
//    }
//    temp_ans = 0;
//    info i;
//    i.x = x; i.y = y; i.day = 1;
//    q.push(i);
//    cout << "시작점 :" << y << "," << x << endl;
//    while (!q.empty()) {
//        int X = q.front().x;
//        int Y = q.front().y;
//        int day = q.front().day;
//        visited[Y][X] = true;
//        //cout << Y << "," << X << ","<<day<<endl;
//        printt();
//        q.pop();
//        temp_ans = max(temp_ans, day);
//        for (int i = 0; i < 4; i++) {
//            int nx = X + px[i];
//            int ny = Y + py[i];
//            if (visited[ny][nx])continue;
//            if (ny <= 0 || ny > N || nx <= 0 || nx > N)continue;
//            if (map[Y][X] >= map[ny][nx]) continue;
//            info ni;
//            ni.x = nx; ni.y = ny; ni.day = day + 1;
//            q.push(ni);
//            visited[ny][nx] = true;
//            qq.push(ni);
//        }
//    }
//    visited[y][x] = false;
//    ans = max(temp_ans, ans);
//}
 
void dfs(int x, int y) {
    int v = 0;
    //cout << y << "," << x << "," << cnt << endl;
    for (int i = 0; i < 4; i++) {
        int nx = x + px[i];
        int ny = y + py[i];
        if (ny <= 0 || ny > N || nx <= 0 || nx > N)continue;
        if (map[y][x] >= map[ny][nx]) continue;
        dfs(nx, ny);
        if (v < visited[ny][nx]) v = visited[ny][nx];
 
    }
    visited[y][x] = v + 1;
    ans = max(ans, visited[y][x]);
}
 
int main() {
    cin >> N;
    for (int y = 1; y <= N; y++) {
        for (int x = 1; x <= N; x++) {
            cin >> map[y][x];
        }
    }
 
    ans = 0;
 
    for (int y = 1; y <= N; y++)
        for (int x = 1; x <= N; x++) {
            //cout << "시작점 :" << y << "," << x << endl;
            if (visited[y][x])continue;
            dfs(x, y);
            //printt();
            //bfs(x, y);
        }
 
    cout << ans;
    
}

풀이

처음에는 bfs로 접근하여 시간초과가 발생하였고 

dfs로 접근하여 풀었을때역시 시간초과가 발생하였습니다.

그리하여 dp로 접근하여 풀었는데 역시 시간초과가 발생하여 계속 고민중인 문제입니다.

조금만 더 고민해보도록 하겠습니다.