글 읽기 - bfs로 push할때 방문표시를 하였는데도 무한루프에 빠집니다

klasnkv 3년 전 0

bfs로 문제를 풀려는 중인데 queue에 push하면서 해당 좌표를 방문표시해서 풀었지만 메모리초과가 계속 나옵니다.

도움 부탁드립니다.

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int board[101][101];
int vis[101][101];
int rain[101][101];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int heightmax=0;
    int maxnum=0;
    int num=0;
    queue<pair<int,int>> Q;
    int K;
    cin>>K;
    for(int i=0;i<K;i++){
        for(int j=0;j<K;j++){
            cin>>board[i][j];
            heightmax=max(heightmax,board[i][j]);
        }
    }

    for(int h=0;h<=heightmax;h++){
        for(int i=0;i<K;i++){
            for(int j=0;j<K;j++){
                
                if(board[i][j]<=h) {
                    rain[i][j]=1;
                }
            }
        }
        //bfs
        
        for(int m=0;m<K;m++){
            for(int n=0;n<K;n++){
                
                if(rain[m][n]==0 && vis[m][n]==0) {
                    num++;
                
                    vis[m][n]=1;
                    Q.push({m,n});
                 
                    while(!Q.empty()){
                        auto cur=Q.front(); Q.pop();
                        for(int i=0;i<4;i++){
                            int nx= cur.X + dx[i];
                            int ny= cur.Y + dy[i];
                            if(nx<0 || ny<0 || nx>=K || ny>=K) continue;
                            if(vis[nx][ny]==1 || rain[nx][ny]==1) continue;
                            vis[nx][ny]==1;
                            Q.push({nx,ny});
                            
                        }
                    }
                }
            }
        }
        maxnum=max(maxnum,num);
        
   
    cout << maxnum;

}

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

문제

문제

출처

ICPC

bfs로 push할때 방문표시를 하였는데도 무한루프에 빠집니다

klasnkv 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말