글 읽기 - 14502번 잘모르겠습니다

rlarbtkd0517 1년 전 0

계속 해서 메모리 초과가 나오는데 어디가 잘못된지 모르겠습니다.

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

int a,b,c=0;
struct att{
    int n;
    int vi=0;
}ans[9][9];

att vans[9][9];

void bfs(){
    queue<pair<int,int>>q;
    for(int i=1;i<=a;++i){
        for(int j=1;j<=b;++j){
            if(ans[i][j].n==2) q.push({i,j});
        }
    }
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        ans[x][y].vi=1;
        if(ans[x+1][y].n==0)q.push({x+1,y});
        if(ans[x-1][y].n==0)q.push({x-1,y});
        if(ans[x][y+1].n==0)q.push({x,y+1});
        if(ans[x][y-1].n==0)q.push({x,y-1});
    }
    int cnt=0;
    for(int i=1;i<=a;++i){
        for(int j=1;j<=b;++j){
            if(ans[i][j].vi==0&&ans[i][j].n==0)cnt++;
        }
    }
    c=max(c,cnt);
}

void retu(){
    for(int i=1;i<=a;++i){
        for(int j=1;j<=b;++j){
            vans[i][j].n=ans[i][j].n;
            vans[i][j].vi=0;
        }
    }
}

void wall(int cnt1){
    if(cnt1==3){
        bfs();
        return;
    }
    for (int i = 1; i <= a; i++){
        for (int j = 1; j <= b; j++){
            if(vans[i][j].n==0){
                vans[i][j].n = 1;
                wall(cnt1+1);
                //기존의 1을 0으로 바꿔줌
                vans[i][j].n = 0;
            }
        }
    }
}

int main(){

    cin>>a>>b;
    for(int i=1;i<=a;++i){
        for(int j=1;j<=b;++j){
            int t;
            cin>>t;
            ans[i][j].n=t;
        }
    }
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j < b; j++) {
            if(ans[i][j].n == 0){
                retu();
                vans[i][j].n =1;
                wall(1);
                vans[i][j].n = 0;
            }
        }
    }
    cout<<c;
}

rmstjd23 1년 전 0

메모리 초과는 27~30 라인을 수정하면 해결가능합니다.

큐에 넣은뒤, 넣은 좌표에대한 visit 체크를 하지않고 큐에서 뺄때 체크한다면

한 좌표에 대해 최대 4번까지 중복해서 들어 갈 수 있는 상황입니다. (임의의 한 좌표에 상, 하, 좌, 우 에서 모두 임의 좌표를 큐에 넣음)

그 4개의 중복 데이터가 다시 또 4개의 중복데이터 (그러니까 4 * 4개의 중복데이터) 를 만들어내는식으로 큐에 중복데이터가 매우 많이 들어갈수 있습니다.

rlarbtkd0517 1년 전 0

정말 감사합니다 ㅠㅠ 피곤한채로 해서 기본을 실수했네요

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

문제

문제

출처

ICPC

14502번 잘모르겠습니다

rlarbtkd0517 1년 전 0

rmstjd23 1년 전 0

rlarbtkd0517 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말