글 읽기 - C++ 메모리 초과 원인을 못찾겠습니다. ㅠㅠ

kjhh03 4년 전 0

51 * 51 배열 하나와

8 * 2 배열 하나 생성하였습니다.

BFS 방식으로 전 맵을 돌며 값을 수정하여 count하여 섬의 개수를 추적하는 방식으로 하였으나

왜 메모리 초과가 나는지 원인을 찾지 못하겠습니다.

제발 도와주세요. ㅠㅠ

#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

int w, h, cnt = 0;
int map[51][51];
int dxy[8][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1} };
queue <pair <int, int> > que;

void bfs(int x, int y) {
	que.push(make_pair(x, y));

	while (!que.empty()){
		for (int i = 0; i < 8; i++) {
			int dx = que.front().second + dxy[i][1];
			int dy = que.front().first + dxy[i][0];
			if (0 <= dx && dx <= h && 0 <= dy && dy <= w && map[dy][dx] == 1) {
				que.push(make_pair(dy, dx));
				map[dy][dx] = map[que.front().first][que.front().second + 1];
			}
		}
		que.pop();
	}
}

void solution() {
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (map[i][j] == 1) {
				bfs(i, j);
				cnt++;
			}
		}
	}

}

int main(int argc, char* argv[]) {
	while (true) {
		cin >> w >>  h;
		if (!w && !h) break;
		memset(map, 0, sizeof(map));
		cnt = 0;
		solution();
		cout << cnt << "\n";
	}
 }

dyk777 4년 전 2

방문 처리가 없어서, 이미 방문한 점이 계속해서 큐에 들어가게 됩니다.

kjhh03 4년 전 0

dyk777

감사합니다.

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

문제

문제

출처

ICPC

C++ 메모리 초과 원인을 못찾겠습니다. ㅠㅠ

kjhh03 4년 전 0

dyk777 4년 전 2

kjhh03 4년 전 0

dyk777

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말