글 읽기 - 메모리 초과

bgy7005 5년 전 1

어느부분에서 메모리 초과가 나는 건지 잘 모르겠습니다..

#include <stdio.h>
#include <algorithm>
#include <deque>
using namespace std;

deque < pair <int, int> > Q;
deque < pair <int, int> > temp;

int main() {
	int w = 1, h = 1, count, h_temp, w_temp;
	int i, j;
	int map[51][51], visited[51][51];
	while (1) {
		scanf("%d %d", &w, &h);
		if (w == 0 && h == 0)
			break;
		//setting
		count = 0;
		for (i = 0; i < h; i++) {
			for (j = 0; j < w; j++) {
				scanf("%d", &map[i][j]);
				visited[i][j] = 0;
				if (map[i][j] == 1)
					Q.push_back(pair<int, int> (i, j));
			}
		}
		//start
		while (!Q.empty()) {
			h_temp = Q.front().first, w_temp = Q.front().second, Q.pop_front();
			//printf("pop : %d %d\n", h_temp, w_temp);
			if (visited[h_temp][w_temp] == 1)
				continue;
			visited[h_temp][w_temp] = 1;
			//printf("setting visited\n");
			//현재 pop된 곳과 연결 되어있는 곳이 있으면 push
			if (0 <= h_temp - 1 && 0 <= w_temp - 1 && map[h_temp - 1][w_temp - 1] == 1 && visited[h_temp - 1][w_temp - 1] == 0)
				temp.push_back(pair<int, int>(h_temp - 1, w_temp - 1));
			if (0 <= h_temp -1 && map[h_temp - 1][w_temp] == 1 && visited[h_temp - 1][w_temp] == 0)
				temp.push_back(pair<int, int>(h_temp - 1, w_temp));
			if (0 <= h_temp - 1 && w_temp + 1 < w && map[h_temp - 1][w_temp + 1] == 1 && visited[h_temp - 1][w_temp + 1] == 0)
				temp.push_back(pair<int, int>(h_temp - 1, w_temp + 1));
			if (w_temp + 1 < w && map[h_temp][w_temp + 1] == 1 && visited[h_temp][w_temp + 1] == 0)
				temp.push_back(pair<int, int>(h_temp, w_temp + 1));
			if (w_temp + 1 < w && h_temp + 1 < h &&  map[h_temp + 1][w_temp + 1] == 1 && visited[h_temp + 1][w_temp + 1] == 0)
				temp.push_back(pair<int, int>(h_temp + 1, w_temp + 1));
			if (h_temp + 1 < h && map[h_temp + 1][w_temp] == 1 && visited[h_temp + 1][w_temp]==0)
				temp.push_back(pair<int, int>(h_temp + 1, w_temp));
			if (0 <= w_temp - 1 && map[h_temp][w_temp - 1] == 1 && visited[h_temp][w_temp - 1] == 0)
				temp.push_back(pair<int, int>(h_temp, w_temp - 1));
			if (0 <= w_temp - 1 && h_temp + 1 < h && map[h_temp + 1][w_temp - 1] == 1 && visited[h_temp + 1][w_temp - 1] == 0)
				temp.push_back(pair<int, int>(h_temp + 1, w_temp - 1));
			//연결 된 곳 모두 찾아서 visited 표시하고, 더이상 없을 때, 섬 개수 ++
			while (!temp.empty()) {
				h_temp = temp.front().first, w_temp = temp.front().second, temp.pop_front();
				visited[h_temp][w_temp] = 1;
				if (0 <= h_temp - 1 && 0 <= w_temp - 1 && map[h_temp - 1][w_temp - 1] == 1 && visited[h_temp - 1][w_temp - 1] == 0)
					temp.push_back(pair<int, int>(h_temp - 1, w_temp - 1));
				if (0 <= h_temp - 1 && map[h_temp - 1][w_temp] == 1 && visited[h_temp - 1][w_temp] == 0)
					temp.push_back(pair<int, int>(h_temp - 1, w_temp));
				if (0 <= h_temp - 1 && w_temp + 1 < w && map[h_temp - 1][w_temp + 1] == 1 && visited[h_temp - 1][w_temp + 1] == 0)
					temp.push_back(pair<int, int>(h_temp - 1, w_temp + 1));
				if (w_temp + 1 < w && map[h_temp][w_temp + 1] == 1 && visited[h_temp][w_temp + 1] == 0)
					temp.push_back(pair<int, int>(h_temp, w_temp + 1));
				if (w_temp + 1 < w && h_temp + 1 < h &&  map[h_temp + 1][w_temp + 1] == 1 && visited[h_temp + 1][w_temp + 1] == 0)
					temp.push_back(pair<int, int>(h_temp + 1, w_temp + 1));
				if (h_temp + 1 < h && map[h_temp + 1][w_temp] == 1 && visited[h_temp + 1][w_temp] == 0)
					temp.push_back(pair<int, int>(h_temp + 1, w_temp));
				if (0 <= w_temp - 1 && map[h_temp][w_temp - 1] == 1 && visited[h_temp][w_temp - 1] == 0)
					temp.push_back(pair<int, int>(h_temp, w_temp - 1));
				if (0 <= w_temp - 1 && h_temp + 1 < h && map[h_temp + 1][w_temp - 1] == 1 && visited[h_temp + 1][w_temp - 1] == 0)
					temp.push_back(pair<int, int>(h_temp + 1, w_temp - 1));
			}
			count++;
			//printf("plus (%d)\n", count);
		}
		printf("%d\n", count);

	}
}

djm03178 5년 전 3

BFS에서는 큐에서 뺄 때가 아니라 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않습니다.

poby 3년 전 0

2년전 글이지만 도움이 되었습니다! 감사합니다

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

문제

문제

출처

ICPC

메모리 초과

bgy7005 5년 전 1

djm03178 5년 전 3

poby 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말