글 읽기 - 5427. 불 // 메모리 초과가 왜 나는지 모르겠어요 ㅠㅠㅠ 도와주세요(C++)

woong611 6년 전 0

메모리 초과가 왜 나는지 모르겠어요 ㅠㅠㅠ 도와주세요(C++)

#include <iostream>
#include <queue>

using namespace std;

int T;
char map[1000][1000];
int re = 0;
int W, H;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
struct person
{
	int r;
	int c;
};

struct fire
{
	int r;
	int c;
};
void init() {
	re = 0;
}

bool checkRange(int _r, int _c) {
	
	if (_r >= 0 && _r < H && _c >= 0 && _c < W) {
		return true;
	}
	else {
		return false;
	}
}

void gogo(int _time, queue<person> _qp, queue<fire> _qf) {

	queue<person> next_qp;
	queue<fire> next_qf; 


	/*
	cout << "시간 : " << _time << endl;
	cout << "큐 사이즈 : " << "_qp : " << _qp.size() << "   _qf : " << _qf.size() << endl;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}

	cout << endl << endl;
	*/
	while (!_qf.empty()) {
		//불 먼저 퍼트리기
		fire temp_f = _qf.front();
		_qf.pop();
		for (int dir = 0; dir < 4; dir++) {
			int next_fr = temp_f.r + dy[dir];
			int next_fc = temp_f.c + dx[dir];

			if (checkRange(next_fr, next_fc) && (map[next_fr][next_fc] != '#' && map[next_fr][next_fc] != '*')) {
				//불꽃은 맵 범위 안에서와 벽만 아니면 이동할 수 있음
				map[next_fr][next_fc] = '*'; //불꽃 설치
				fire next_fire{ next_fr, next_fc };
				next_qf.push(next_fire);
			}
		}
	}

	while (!_qp.empty()) {

		person temp_p = _qp.front();
		_qp.pop();

		for (int dir = 0; dir < 4; dir++) {
			int next_pr = temp_p.r + dy[dir];
			int next_pc = temp_p.c + dx[dir];

			if (checkRange(next_pr, next_pc) && map[next_pr][next_pc] == '.') {

				if (next_pr == 0 || next_pr == (H - 1) || next_pc == 0 || next_pc == (W - 1)) {
					//도착
					cout << _time + 1 << endl;
					return;
				}

				//사람은 맵 범위 안에서와 빈공간일 때 이동할 수 있음
				map[next_pr][next_pc] = '@';
				person next_p{ next_pr, next_pc };
				next_qp.push(next_p);
			}
		}
	}
	

	if (!next_qp.empty()) {
		//이동 할 수 있다면
		gogo(_time + 1, next_qp, next_qf);
	}
	else {
		//실패
		cout << "IMPOSSIBLE" << endl;
	}

	
}

int main() {

	cin >> T;

	for (int tc = 1; tc <= T; tc++) {
		
		cin >> W >> H;
		queue<person> pq;
		queue<fire> fq;

		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				cin >> map[i][j];
				if (map[i][j] == '@') {
					person p{i, j};
					pq.push(p);
					continue;
				}

				if (map[i][j] == '*') {
					fire temp_f{ i, j };
					fq.push(temp_f);
				}
			}
		}
		gogo(1, pq, fq);

	}

	return 0;
}

djm03178 6년 전 1

gogo 함수를 호출할 때마다 큐의 모든 내용이 복사되어 새로운 큐에 들어가고, 재귀호출이 깊어질수록 점점 더 많은 요소가 쌓여갑니다.

이를 피하려면 참조자나 포인터를 쓰거나, 재귀 대신 반복문으로 해결하면 됩니다.

woong611 6년 전 0

네 감사합니다. 덕분에 해결했습니다!

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

문제

문제

출처

ICPC

5427. 불 // 메모리 초과가 왜 나는지 모르겠어요 ㅠㅠㅠ 도와주세요(C++)

woong611 6년 전 0

djm03178 6년 전 1

woong611 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말