글 읽기 - bfs 메모리 초과

noobwd 4년 전 0

다른분들 질문 다찾아봤는데도 모르겠네요... 가장 흔한 백준 bfs 메모리 초과 문제입니다. 방문체크 다 했는데도 계속 그러네요

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

using namespace std;

int m, n;

bool map[101][100] = { 0, };
bool check[101][100] = { 0, };

queue<int>orderX;
queue<int>orderY;

void fill(int y, int x)
{
	check[y][x] = 1;
	if (y < n - 1 && !check[y + 1][x] && map[y + 1][x])
	{
		orderX.push(x);
		orderY.push(y + 1);
	}
	if (y > 0 && !check[y - 1][x] && map[y - 1][x])
	{
		orderX.push(x);
		orderY.push(y - 1);
	}
	if (x < m - 1 && !check[y][x + 1] && map[y][x + 1])
	{
		orderX.push(x + 1);
		orderY.push(y);
	}
	if (x > 0 && !check[y][x-1] && map[y][x-1])
	{
		orderX.push(x - 1);
		orderY.push(y);
	}
}

int main()
{
	int count;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		char input[10001];
		cin >> input;
		for (int j = 0; j < m; j++)
			if (input[j] == '1') map[i][j] = 1;
			else map[i][j] = 0;
	}
	orderX.push(0);
	orderY.push(0);
	for (count = 0; ; count++)
	{
		int finalle = 0;
		for (int i = orderX.size(); i > 0; i--)
		{
			if (orderX.front() == m - 1 && orderY.front() == n - 1)
				finalle = 1;
			fill(orderY.front(), orderX.front());
			orderY.pop();
			orderX.pop();
		}
		if (finalle == 1) break;
	}
	cout << count + 1;
	return 0;
}

inc5025 4년 전 1

orderX와 orderY에 push할때가 아닌 fill을 실행시킬때 check를 1로 만들어 방문했다는 표시를 남기기 때문에

큐에 중복된 지점이 여러번 들어갈 수 있습니다.

push와 동시에 check를 1로 만들어주면 정상적으로 작동합니다.

noobwd 4년 전 0

아 결국 다른글들을 제데로 안읽은거네요

감사합니다, 수정 되었습니다!

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

문제

문제

출처

ICPC

bfs 메모리 초과

noobwd 4년 전 0

inc5025 4년 전 1

noobwd 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말