글 읽기 - 메모리초과의 이유가 뭘까요?

seojeongwook2 5년 전 0

BFS돌리는 함수 반환형을 int로 해서 한번 BFS동안 방문한 배열의 갯수를 return하면 메모리 초과가 발생하고,

반환형을 void로 해서 전역변수를 바꿔주는 코드는 AC를 맞습니다..

이유가 무엇인지 알 수 있을까요?'

아래코드가 메모리초과 발생하는 코드입니다.

#pragma once
#pragma warning(disable:4996) 

#include<bits/stdc++.h>
using namespace std;

#define MIN(a, b) ((a > b) ? b : a)
#define MAX(a, b) ((a > b) ? a : b)
#define INF 0x3FFFFFFF
#define iINF 0x7FFFFFFF
#define uiINF 0xFFFFFFFF

typedef long long ll;
typedef unsigned long long ull;
typedef struct Point { int x, y; } Point;
typedef pair<int, int> pii;
typedef struct Node { int data; Node* prev; } Node;
/*
const int dirx[] = { 0,0,1,-1,1,-1,1,-1 };
const int diry[] = { 1,-1,0,0,1,1,-1,-1 };
*/

const int dirx[] = { -1,0,1,0 };
const int diry[] = { 0,-1,0,1 };

#define MAX_SIZE 52

/* input data */
int N, M;
int input[MAX_SIZE][MAX_SIZE];
int visit[MAX_SIZE][MAX_SIZE];
int indsize[MAX_SIZE * MAX_SIZE];
int cnt, maxsize;
queue<pii> q;

/* function */
int BFS(int, int, int);


int main(int argc, char* argv[]) {
	ios::sync_with_stdio(false); cin.tie(NULL);
	// setbuf(stdout, NULL);
	scanf("%d %d", &M, &N);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &input[i][j]);
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (visit[i][j] == 0) {
				indsize[++cnt] = BFS(cnt, j, i);
				maxsize = MAX(maxsize, indsize[cnt]);
			}
		}
	}

	int Ans = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			for (int k = 0; k < 4; k++) {
				int kx = j + dirx[k];
				int ky = i + diry[k];

				if (kx < 0 || ky < 0 || kx >= M || ky >= N) { continue; }
				if (visit[i][j] != visit[ky][kx]) {
					Ans = MAX(Ans, indsize[visit[i][j]] + indsize[visit[ky][kx]]);
				}
			}
		}
	}



	printf("%d\n%d\n%d", cnt, maxsize, Ans);
	return 0;
}

int BFS(int ind, int sx, int sy) {
	int cntroom = 1;
	q.push(make_pair(sx, sy));
	visit[sy][sx] = ind;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		
		q.pop();

		for (int i = 0; i < 4; i++) {
			int kx = x + dirx[i];
			int ky = y + diry[i];

			if (kx < 0 || ky < 0 || kx >= M || ky >= N || visit[ky][kx] != 0) { continue; }

			if ((input[y][x] & (1 << i)) == 0) {
				q.push(make_pair(kx, ky));
				visit[ky][kx] = ind;
				cntroom++;
			}
		}
	}
	return cntroom;
}

doded12 3년 전 0

단순 visited를 체크하실거면 bool로 선언해주시는게 좋아요!

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

문제

문제

출처

ICPC

메모리초과의 이유가 뭘까요?

seojeongwook2 5년 전 0

doded12 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말