글 읽기 - 2178번 BFS메모리 초과ㅠㅜ

dlswmd08 5년 전 1

BFS에서 메모리 초과 일어나서 주의사항까지 확인했는데 왜 일어났는지 모르겠네요 ㅠㅜ

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

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

class Graph{
public:
	int lX,lY;
	bool map[100][100];
	queue<pair<int,int> > Q;
	bool visited[100][100];
	
	Graph() : lX(0), lY(0){
	}	
	
	Graph(int n, int m) : lX(n), lY(m){
	}
	
	void addMap(int x, int y, bool data){
		map[x][y] = data;
	}
	
	int bfs(){
		Q.push(make_pair(0,0));
		pair<int,int> finish = make_pair(lX-1,lY-1);
		int cnt = 1;
		pair<int, int> next = Q.front();
		Q.pop();
		search(next);
		while(!Q.empty()){
			cnt++;
			int qSize = Q.size();
			for(int i=0; i < qSize; i++){
				pair<int, int> next = Q.front();
				Q.pop();
				if(next == finish){
					return cnt;	
				}
				search(next);				
			}
		}
		return -1;
	}

private:
	void search(pair<int, int> cor){
		if( cor.first >= lX || cor.second >= lY || cor.first < 0 || cor.second < 0) return;	
		visited[cor.first][cor.second] = true;		
		for(int i =0; i < 4; i++){
			pair<int, int> next_pair = make_pair(cor.first+dx[i], cor.second+dy[i]);
			if(!visited[next_pair.first][next_pair.second] && map[next_pair.first][next_pair.second]){
				Q.push(next_pair);
			}
		}
	}
};
int main()
{
	int n , m;
	cin >> n >> m;
	
	Graph G(n,m);
	
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			int n;
			scanf("%1d", &n);
			G.addMap(i,j,n);
		}
	}
	
	cout << G.bfs();
}

djm03178 5년 전 1

주의사항이라는 게 https://www.acmicpc.net/board/... 를 말씀하시는 건가요?

"큐에서 뺀 뒤에 방문 여부를 표시하면 동시에 여러 칸으로부터 큐에 중복해서 삽입하게 되므로, 큐에 넣을 때 방문했음을 바로 표시하는 게 바람직합니다."

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

문제

문제

출처

ICPC

2178번 BFS메모리 초과ㅠㅜ

dlswmd08 5년 전 1

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말