글 읽기 - 아기상어 메모리초과

gyrkf 4년 전 0

어떤 부분이 메모리초과를 일으키는지 모르겠네요;

큐랑 벡터는 다 클리어되는것 같은데 고수님들 도와주세요!

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 30;
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};

struct POS{
    int x;
    int y;
};

struct INFO{
    
    POS p;
    int dis;
    
};

int time_chk[MAX][MAX];
int map[MAX][MAX];
bool visited[MAX][MAX];
int n;
int ans;
int cnt;
int size = 2;

queue<POS>q;
vector<INFO>v;

bool cmp(INFO a, INFO b){
    
    if(a.dis == b.dis){
        if(a.p.x == b.p.x) return a.p.y < b.p.y;
        else return a.p.x < b.p.x;
    }
    else return a.dis < b.dis;
    
}

void Init(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            visited[i][j] = false;
            //time_chk[i][j] = 0;
        }
    }
    v.clear();
}

void BFS(){
    
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        q.pop();
        
        for(int i=0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(nx>=0 && ny >=0 && nx<n && ny<n && map[nx][ny] <= size && !visited[nx][ny]){
                time_chk[nx][ny] = time_chk[x][y] + 1;
                visited[x][y] = true;
                
                if(map[nx][ny] != 0 && map[nx][ny] < size){
                    v.push_back({nx,ny,time_chk[nx][ny]});
                }

                q.push({nx,ny});
            }
        }      
    }
}


int main(){

    scanf("%d",&n);
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d",&map[i][j]);
            if(map[i][j] == 9){
                q.push({i,j});
                map[i][j] = 0;
                visited[i][j] = true;
            }
        }
    }
    
    while(1){
        
        BFS();
        
        if(v.size() == 0) break;
    
        sort(v.begin(),v.end(),cmp);
      
        map[v[0].p.x][v[0].p.y] = 0;
    
        ans = time_chk[v[0].p.x][v[0].p.y];
        cnt++;
    
        if(cnt >= size){
            cnt = 0;
            size++;
        }
        
        q.push({v[0].p.x,v[0].p.y});
        Init();
        
        visited[v[0].p.x][v[0].p.y] = true;
        v.clear();
        
    };
    printf("%d",ans);
    
    return 0;
}

3587jjh 4년 전 1

67째줄이 문제인듯 합니다

gyrkf 4년 전 1

BFS 할때 67번째줄 보시면, 다음위치 nx,ny에 대한 방문여부를 체크해야하는데 x,y로 체크해버려서

중복으로 인해 큐에 필요없는 데이터들이 쌓이다보니 큐가 터져서 메모리 초과발생하였습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

아기상어 메모리초과

gyrkf 4년 전 0

3587jjh 4년 전 1

gyrkf 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말