글 읽기 - [17130 C++] BFS로 했더니, 메모리 초과가 뜨는데 어떻게 해야할까요?

mycool0905 4년 전 0

모든 경우를 다 계산해봐야한다는 생각에, 방문여부 체크하는 bool 배열 visited도 일부러 안만들었구요.

혹시나 당근 수가 제일 큰거만 먼저 보내보자는 생각에 우선순위 큐도 이용해봤는데, 그러면은 시간초과가 발생하더라구요. ( 아마도 Max Heap 처리과정인듯 )

혹시 이 문제에 대해 추가 설명이나 충고좀 해주실 수 있을까요?

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

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

typedef struct rabbit {
	int x;
	int y;
	int c;
}rabbit;

using namespace std;

int N, M;
char map[1000][1001];
int maxValue = -1;

bool isIn(int x, int y)
{
	if (0 <= x && x < N && 0 <= y && y < M)
		return true;
	else
		return false;
}

void BFS(rabbit start)
{
	queue<rabbit> Queue;
	rabbit newRabbit;
	int newX, newY;

	Queue.push(start);

	while (!Queue.empty())
	{
		newRabbit = Queue.front();
		Queue.pop();

		for (int i = 0; i < 3; i++)
		{
			newX = newRabbit.x + dx[i];
			newY = newRabbit.y + dy[i];

			if (isIn(newX, newY))
				if (map[newX][newY] == 'O')
				{
					Queue.push({ newX,newY,newRabbit.c });
					maxValue = max(maxValue, newRabbit.c);
				}
				else if (map[newX][newY] == 'C')
					Queue.push({ newX,newY,newRabbit.c + 1 });
				else if (map[newX][newY] == '.')
					Queue.push({ newX,newY,newRabbit.c });
		}
	}
}

int main()
{
	bool startFlag = false;
	rabbit start;
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		cin >> map[i];
		if (!startFlag)
			for (int j = 0; j < M; j++)
				if (map[i][j] == 'R')
				{
					start = { i,j,0 };
					startFlag = true;
				}
	}

	BFS(start);

	cout << maxValue << "\n";

	return 0;
}