글 읽기 - 메모리초과 라는데..어디가 문제일까요?

sukwoo0711 6년 전 0

메모리초과 날만한 부분이 큐인것같은데..

중복되는 원소는 삽입안되게끔 처리한 것 같은데 문제가 발생하네요.

알고리즘은 아래처럼 구현했어요

BFS시 모든 동작을 다 함(할 수 있으면 하고, 못하면 RETURN;)

visit[x][y][z] 로 방문여부를 관리했고, 중복삽입을 막기위해서

if (visit[x-1][y][z] > visit[x][y][z]+1)

=> visit[x-1][y][z] = visit[x][y][z]+1; //추후 같은위치에 방문 시, 더 낮은값으로 세팅이 되어있기때문에 추가하지 않음

코드 지적좀 부탁드립니다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int getVertical(int x, int y);
char map[51][51];
int visit[51][51][2];
int n, m, bx, by, bz, ex, ey, ez;
int b_count, e_count, ex_b_count, ex_e_count;
struct obj {
	int x, y, z;
	obj(int a, int b, int c) : x(a), y(b), z(c) {};
};
queue <obj> que;
queue <obj> answer;
void output()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			printf("[%d/%d]", visit[i][j][0], visit[i][j][1]);
		}
		puts("");
	}
	puts("");
}
void input()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%s", &map[i]);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			visit[i][j][0] = visit[i][j][1] = 10000;
			if (map[i][j] == 'B')
			{
				b_count++;
				if (b_count == 2)
				{
					bx = i;
					by = j;
				}
			}
			if (map[i][j] == 'E')
			{
				e_count++;
				if (e_count == 2)
				{
					ex = i;
					ey = j;
				}
			}
		}
	}
	bz = getVertical(bx, by);
	ez = getVertical(ex, ey);
	que.push(obj(bx, by, bz));
	answer.push(obj(ex, ey, ez));

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (map[i][j] == 'E')
				map[i][j] = '0';
		}
	}
}
int getVertical(int x, int y)
{
	if (map[x][y] == map[x - 1][y] && map[x + 1][y] == map[x][y])
		return 1;
	else
		return 0;
}
bool move_U(int x, int y, int z)
{
	//Hor
	bool OK = true;
	if (z == 0)
	{
		for (int i = -1; i <= 1; i++)
		{
			if (map[x - 1][y + i] != '0')
				return false;
		}
		if (visit[x - 1][y][z] >=visit[x][y][z] + 1)
		{
			visit[x - 1][y][z] = visit[x][y][z] + 1;
			que.push(obj(x - 1, y, z));
		}
	}
	//Ver
	else if (z == 1)
	{
		if (x - 2 < 0)
			return false;
		else
		{
			if (map[x - 2][y] != '0')
				OK = false;
			else
			{
				if (visit[x - 1][y][z] >= visit[x][y][z] + 1)
				{
					visit[x - 1][y][z] = visit[x][y][z] + 1;
					que.push(obj(x - 1, y, z));
				}
			}
		}
	}
	return OK;
}
bool move_D(int x, int y, int z)
{
	//Hor
	bool OK = true;
	if (z == 0)
	{
		for (int i = -1; i <= 1; i++)
		{
			if (map[x + 1][y + i] != '0')
				return false;
		}
		if (visit[x + 1][y][z] >= visit[x][y][z]+1)
		{
			visit[x + 1][y][z] = visit[x][y][z] + 1;
			que.push(obj(x + 1, y, z));
			
		}
	}
	//Ver
	else if (z == 1)
	{
		if (x + 2 > n)
			return false;
		else
		{
			if (map[x + 2][y] != '0')
				OK = false;
			else
			{
				if (visit[x + 1][y][z] >=visit[x][y][z]+1)
				{
					visit[x + 1][y][z] = visit[x][y][z] + 1;
					que.push(obj(x + 1, y, z));
				}
			}
		}
	}
	return OK;
}
bool move_L(int x, int y, int z)
{
	//ver
	bool OK = true;
	if (z == 1)
	{
		for (int i = -1; i <= 1; i++)
		{
			if (map[x + i][y - 1] != '0')
				return false;
		}
		if (visit[x][y - 1][z] >= visit[x][y][z]+1)
		{
			visit[x][y - 1][z] = visit[x][y][z] + 1;
			que.push(obj(x, y - 1, z));
		}
	}
	//Ver
	else if (z == 0)
	{
		if (y - 2 < 0)
			return false;
		else
		{
			if (map[x][y - 2] != '0')
				OK = false;
			else
			{
				if (visit[x][y - 1][z] >=visit[x][y][z]+1)
				{
					visit[x][y - 1][z] = visit[x][y][z] + 1;
					que.push(obj(x, y - 1, z));
				}
			}
		}
	}
	return OK;
}
bool move_R(int x, int y, int z)
{
	//ver
	bool OK = true;
	if (z == 1)
	{
		for (int i = -1; i <= 1; i++)
		{
			if (map[x + i][y + 1] != '0')
				return false;
		}
		if (visit[x][y + 1][z] >=visit[x][y][z]+1)
		{
			visit[x][y + 1][z] = visit[x][y][z] + 1;
			que.push(obj(x, y + 1, z));
		}
	}
	//Ver
	else if (z == 0)
	{
		if (y + 2 >= n)
			return false;
		else
		{
			if (map[x][y + 2] != '0')
				OK = false;
			else
			{
				if (visit[x][y + 1][z] >=visit[x][y][z]+1)
				{
					visit[x][y + 1][z] = visit[x][y][z] + 1;
					que.push(obj(x, y + 1, z));
				}
			}
		}
	}
	return OK;
}
bool move_T(int x, int y, int z)
{
	bool OK = true;
	if (x - 1 < 0 || x + 1 >= n || y - 1 < 0 || y + 1 >= n)
		return false;
	for (int i = x - 1; i <= x + 1; i++)
	{
		for (int j = y - 1; j <= y + 1; j++)
		{
			if (map[i][j] == '1')
				return false;
		}
	}
	if (z == 0)
	{
		if (visit[x][y][1] >=visit[x][y][0]+1)
		{
			visit[x][y][1] = visit[x][y][0] + 1;
			que.push(obj(x, y, 1));
		}
	}
	else
	{
		if (visit[x][y][0] >=visit[x][y][1]+1)
		{
			visit[x][y][0] = visit[x][y][1] + 1;
			que.push(obj(x, y, 0));
		}
	}
}
void process()
{
	visit[bx][by][bz] = 1;
	while (!que.empty())
	{
		int px = que.front().x;
		int py = que.front().y;
		int pz = que.front().z;
		que.pop();
		//output();
		if (px < 0 || px >= n || py < 0 || py >= n)
			continue;
		if (px == ex && py == ey && pz == ez)
		{
			printf("%d\n", visit[px][py][pz] - 1);
			return;
		}
		move_U(px, py, pz);
		move_D(px, py, pz);
		move_L(px, py, pz);
		move_R(px, py, pz);
		move_T(px, py, pz);
	}
	printf("0\n");
}
int main()
{
	input();
	process();
	return 0;
}

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

문제

문제

출처

ICPC

메모리초과 라는데..어디가 문제일까요?

sukwoo0711 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말