글 읽기 - c++ 메모리초과 도움 부탁드립니다ㅠㅠ

youuuuuu 3년 전 0

메모리초과가 계속 발생하네요.. 도움 부탁드립니다

처음에는 토마토상자를 vector로 구현하여 발생하는 문제로 생각하고 vector에서 배열을 전역변수로 선언하여 소스를 수정 제출 하였지만 메모리초과가 발생하였습니다.

다음에는 토마토를 익히는 과정에서 x, y좌표 저장을 위해 queue를 각각 한개씩 선언하여 사용하였는데 이것을 pair로 묶어서 수정 제출 하였지만 역시 메모리초과가 발생하였습니다...

메모리초과 발생하는 이유를 모르겠습니다ㅠㅠㅠㅠ

#include <iostream>
#include <queue>
using namespace std;

//           우 상  하 좌
int dx[4] = { 0, -1, 1, 0 };
int dy[4] = { 1, 0, 0, -1 };
int box_arr[1001][1001] = { 0, };
bool chk_box[1001][1001];
void bfs(int x, int y, int m, int n) {
	queue<pair<int, int>> Queue;
	Queue.push(make_pair(x, y));
	chk_box[x][y] = true;
	while (!Queue.empty()) {
		int q_x = Queue.front().first;
		int q_y = Queue.front().second;
		Queue.pop();

		for (int i = 0; i < 4; i++) {
			int next_x = q_x + dx[i];
			int next_y = q_y + dy[i];

			//토마토 박스 범위 체크
			if (next_x >= 0 && next_x < m && next_y >= 0 && next_y < n) {

				//토마토의 빈칸이 아니라면
				if (box_arr[next_x][next_y] != -1) {
					int cnt = box_arr[q_x][q_y];

					//토마토 칸을 방문 안한경우
					if (!chk_box[next_x][next_y]) {
						Queue.push(make_pair(next_x, next_y));
						if (box_arr[next_x][next_y] != 1) {
							box_arr[next_x][next_y] = cnt + 1;
						}
						chk_box[next_x][next_y] = true;
					}
					else {	//토마토 칸을 방문 한 경우
						if (box_arr[next_x][next_y] > cnt) {
							box_arr[next_x][next_y] = cnt + 1;
							Queue.push(make_pair(next_x, next_y));
						}
					}
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;

	int x, y;
	//토마토박스 입력
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> box_arr[i][j];
			if (box_arr[i][j] == 1) {
				x = i;
				y = j;
			}
		}
	}

	//토마토 익히기
	bfs(x, y, m, n);

	int max = 0;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (box_arr[i][j] == 0) {
				cout << "-1\n";
				return 0;
			}
			else {
				if (max < box_arr[i][j]) {
					max = box_arr[i][j];
				}
			}
		}
	}
	cout << max-1 << '\n';

	return 0;
}

malratz 3년 전 0

예제 3번의 결과값하고, 문제의 조건을 다시한번 확인 해보시면은 좋을 것 같습니다.

"정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다."

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

문제

문제

출처

ICPC

c++ 메모리초과 도움 부탁드립니다ㅠㅠ

youuuuuu 3년 전 0

malratz 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말