글 읽기 - 벽부수고 이동하기2 메모리초과 문제.

leekang9070 5년 전 0

visit를 사용하여 메모리 초과를 최소화 했다고 생각했는데 아닌가보네요..

계속 찾아봐도 찾을 수가 없네요

도움 부탁 드립니다....

#include<iostream>
#include<queue>
using namespace std;

char board[1000][1000];
int visit[1000][1000][11];
int ysize;
int xsize;
int brokenCount;
int result = 1234567;
int dir[4][2] =
{
	{ 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 }
};
class  Point
{
public:
	int y;
	int x;
	int count = 0;
};
queue<Point> q;

void asd()
{
	for (int i = 0; i < ysize; i++)
	{
		for (int j = 0; j < xsize; j++)
		{
			for (int k = 0; k <= brokenCount; k++)
			{
				visit[i][j][k] = -1;
			}
		}
	}
}
void bfs(int y, int x, int count)
{
	if (y == ysize - 1 && x == xsize - 1)
	{
		if (visit[y][x][count] < result)//종결 조건 
		{
			result = visit[y][x][count];
		}
		return;
	}
	else
	{
		for (int i = 0; i < 4; i++)
		{
			if (y + dir[i][0] < ysize && x + dir[i][1] < xsize&&y + dir[i][0] >= 0 && x + dir[i][1] >= 0)
			{
				if (visit[y + dir[i][0]][x + dir[i][1]][count] == -1)//방문하지않았을 경우 
				{
					if (board[y + dir[i][0]][x + dir[i][1]] == '0')//벽이 아닐 경우 
					{
							Point point;
							point.x = x + dir[i][1];
							point.y = y + dir[i][0];
							point.count = count;
							q.push(point);
							visit[y + dir[i][0]][x + dir[i][1]][count] = visit[y][x][count] + 1;
					}
				}
				if (visit[y + dir[i][0]][x + dir[i][1]][count+1] == -1)
				{
					if (board[y + dir[i][0]][x + dir[i][1]] == '1')//벽일 경우
					{
							if (count+1 <= brokenCount)
							{
								Point point;
								point.x = x + dir[i][1];
								point.y = y + dir[i][0];
								point.count = count + 1;
								q.push(point);
								visit[y + dir[i][0]][x + dir[i][1]][count + 1] = visit[y][x][count] + 1;
							}
					}
				}
			}
		}

	}

	while (q.empty() == false)
	{
		Point a = q.front();
		q.pop();
		int x1 = a.x;
		int y1 = a.y;
		int count1 = a.count;

		bfs(y1, x1, count1);
	}



}

int main()
{
	cin >> ysize >> xsize >> brokenCount;

	asd();

	for (int i = 0; i < ysize; i++)
	{
		for (int j = 0; j < xsize; j++)
		{
			cin >> board[i][j];
		}
	}
	for (int i = 0; i <= brokenCount; i++)
	{
	visit[0][0][i] = 1;
	}
	bfs(0, 0, 0);
	if (result == 1234567)
	{
		cout << -1<<endl;
	}
	else
	{
		cout << result<<endl;
	}

}

djm03178 5년 전 0

bfs에서 재귀를 할 필요가 없습니다. 지금처럼 재귀를 하면 갈 수 있는 칸들을 재귀로 매우 깊이 들어가면서 호출 스택에 칸 수에 비례하는 메모리가 쌓이는데 한 번의 호출에 쌓이는 양이 많아 메모리 제한을 넘는 것으로 보입니다.

bfs는 재귀를 하지 말고 그냥 반복문 하나로 돌리면 됩니다.

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

문제

문제

출처

ICPC

벽부수고 이동하기2 메모리초과 문제.

leekang9070 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말