글 읽기 - 메모리초과 질문드립니다.

legendmic2 3년 전 0

BFS를 다시 공부해서, queue를 활용하여 풀었습니다.

근데 또 메모리초과가 떠서...질문드립니다...

이전의 질문에선 매개변수를 계속 새로 생성하다보니 메모리초과가 났는데,

이번엔 어떤 부분에서 메모리초과가 난지 모르겠습니다ㅠㅠ

조언 부탁드립니다. 감사합니다!

#include <iostream>
#include <queue>
#include <string>

#define MAX 1001

using namespace std;

int R, C; // R : 미로 행의 개수 // C : 미로 열의 개수
int start_x, start_y;
int arr[MAX][MAX]; // 미로
// 빈공간 : 0 // 벽, 불 : 1 // 시작점 : 2
bool visit[MAX][MAX]; // 방문여부
queue <pair<int, int>> Fire;
int mov[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; // 상, 하, 좌, 우.
// move[][0] 행번호, move[][1] 열번호

int BFS(int init_x, int init_y)
{
	queue<pair<int, int>> q; // 이전 순번에서 지훈이가 이동한 위치
	q.push(make_pair(init_x, init_y)); // 초기값으로 맨 처음 위치를 저장

	int result = 0; // 몇번 전진했는지
	while (1)
	{
		result++;
		int Fire_size = Fire.size();
		
		// 현재 존재하는 모든 불을 상하좌우로 확산시키자
		while (Fire_size--)
		{
			int x = Fire.front().first;
			int y = Fire.front().second;
			Fire.pop();

			// 불의 상하좌우를 확인
			for (int i = 0; i < 4; ++i)
			{
				int nx = x + mov[i][0];
				int ny = y + mov[i][1];

				if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue; // 미로 외부의 좌표라면 패스
				if (arr[nx][ny] == 1) continue; // 불 또는 벽이라면 패스
				arr[x][y] = 1;
				Fire.push(make_pair(x, y));
			}
		}
		// 불 확산 완료

		int size = q.size();
		if (size == 0) return -1; // 이전 순번에서 지훈이가 이동한 위치가 없다면 -1(불가능) 반환
		
		// 이전 순번에서 지훈이가 이동한 위치들을 안전한 곳(arr[x][y]==0)으로 이동하자
		while (size--)
		{
			int x = q.front().first;
			int y = q.front().second;
			q.pop();

			for (int i = 0; i < 4; ++i)
			{
				int nx = x + mov[i][0];
				int ny = y + mov[i][1];

				if (nx < 0 || nx >= R || ny < 0 || ny >= C) return result;
				// 미로 외부의 좌표라면 탈출한 것이므로 현재까지 전진한 횟수 반환
				if (visit[nx][ny] || arr[nx][ny] == 1) continue;
				// 방문했었거나, 불 또는 벽이라면 패스
				arr[nx][ny] = 2; // 이거 넣을필요가..?
				visit[nx][ny] = true;
				q.push(make_pair(nx, ny));
			}

		}

	}

}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> R >> C;
	
	for (int i = 0; i < R; ++i)
	{
		string temp; cin >> temp;
		for (int j = 0; j < C; ++j)
		{
			if (temp[j] == '#') arr[i][j] = 1;
			else if (temp[j] == 'J')
			{
				start_x = i; start_y = j;
				arr[i][j] = 2;
			}
			else if (temp[j] == 'F')
			{
				Fire.push(make_pair(i, j));
				arr[i][j] = 1;
			}
			else arr[i][j] = 0;
		}
	}

	int check = BFS(start_x, start_y);
	if (check == -1) cout << "IMPOSSIBLE";
	else cout << check;

}

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

문제

문제

출처

ICPC

메모리초과 질문드립니다.

legendmic2 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말