글 읽기 - 거듭된 메모리 초과로 도움! 을 요청합니다.

kinssang 6년 전 0

특별할게 없는 BFS를 사용한 풀이인데요

33% 쯤에 시간 초과도 아니고 메모리 초과가 떠버리니...

시간제한도 0.5초라 제대로 돌려도 시간초과가 뜰 것 같기도 한데

메모리 사용량 줄이는 방법은 어떻게 하는게 좋을까요?

제 체감상 크기가 큰 구조체가 큐에 들어가면서 메모리 사용량이 늘어나는게 문제인 것 같은데

remain, last 같은 애들은 구조체에 속해있지 않지만 remain_check를 통해 계산을 할 수 있긴 합니다.

int y, x도 하나짜리로 통합이 가능하긴 합니다.

어떻게 처리하면 메모리 초과를 피할 수 있을지 고수님들의 도움을 요청드립니다.

#include <stdio.h>
#include <queue>
#include <vector>
#include <string.h>

using namespace std;

typedef struct
{
	int y;
	int x;
	int move;
	int remain;
	int last;
	bool remain_check[4][5] = {};
	bool visit[20][4][5] = {};
}element;

char next(int last)
{
	char target[20] = { '1', '2', '3', '4', '5', '6', '7', '8', '9', };
	for (int i = 9; i < 20; i++) target[i] = 'A' + (i - 9);
	return target[last];
}

int main()
{
	int T, to_x[4] = { -1, 0, 1, 0 }, to_y[4] = { 0, 1, 0, -1 };
	scanf("%d", &T);
	for (int i = 0; i < T; i++)
	{
		char map[4][5];
		int remain_move = 0, start_y, start_x;
		queue<element> Queue;
		for (int j = 0; j < 4; j++)
		{
			for (int k = 0; k < 5; k++)
			{
				scanf(" %c", &map[j][k]);
				if (map[j][k] != '.') remain_move++;
				if (map[j][k] == '0')
				{
					remain_move--;
					start_y = j;
					start_x = k;
				}
			}
		}
		bool IsSuccess = false;
		element temp;
		temp.y = start_y;
		temp.x = start_x;
		temp.move = 0;
		temp.last = 0;
		temp.remain = remain_move;
		temp.remain_check[start_y][start_x] = true;
		temp.visit[0][start_y][start_x] = true;
		Queue.push(temp);
		while (!Queue.empty())
		{
			int y = Queue.front().y, x = Queue.front().x, move = Queue.front().move, last = Queue.front().last, remain = Queue.front().remain;
			if (remain == 0)
			{
				IsSuccess = true;
				printf("%d\n", move);
				break;
			}
			memcpy(temp.remain_check, Queue.front().remain_check, sizeof(temp.remain_check));
			memcpy(temp.visit, Queue.front().visit, sizeof(temp.visit));
			Queue.pop();
			for (int j = 0; j < 4; j++)
			{
				if (y + to_y[j] < 0 || y + to_y[j] > 3 || x + to_x[j] < 0 || x + to_x[j] > 4) continue;
				if (map[y + to_y[j]][x + to_x[j]] == '.') continue;
				if (map[y + to_y[j]][x + to_x[j]] != '#' && map[y + to_y[j]][x + to_x[j]] > next(last)) continue;
				if (temp.visit[last][y + to_y[j]][x + to_x[j]]) continue;

				temp.y = y + to_y[j];
				temp.x = x + to_x[j];
				temp.move = move + 1;
				temp.remain = remain;
				temp.last = last;

				bool remain_changed = false;

				if (!temp.remain_check[temp.y][temp.x])
				{
					temp.remain_check[temp.y][temp.x] = true;
					temp.remain = remain - 1;
					remain_changed = true;
				}

				if (map[y + to_y[j]][x + to_x[j]] == '#' || (map[y+to_y[j]][x+to_x[j]] != '#' && map[y+to_y[j]][x+to_x[j]] < next(last)))
				{
					temp.visit[last][y + to_y[j]][x + to_x[j]] = true;
					Queue.push(temp);
					temp.visit[last][y + to_y[j]][x + to_x[j]] = false;
				}
				else if (map[y + to_y[j]][x + to_x[j]] == next(last))
				{
					temp.visit[last + 1][y + to_y[j]][x + to_x[j]] = true;
					temp.last = last + 1;
					Queue.push(temp);
					temp.visit[last + 1][y + to_y[j]][x + to_x[j]] = false;
				}

				if (remain_changed) temp.remain_check[temp.y][temp.x] = false;
			}
		}
		if (!IsSuccess) printf("-1\n");
	}
	return 0;
}