글 읽기 - C++ 메모리 초과 해결하는 방법 있나요,,, (14%)

zmxncbv777 2년 전 0

14%에서 자꾸만 메모리초과가 나옵니다.

섬마다 번호 붙이고 (가장자리가 아닌 내부에서는 -1을 가짐)

섬의 번호가 붙어있는 지역에서 다른 번호를 가진 섬까지 도달하는 거리를 찾는 bfs를 돌렸습니다.

예제 맞게 나오는 것 확인했는데 메모리 초과가 나오네요,,,

메모리 초과가 나오는 이유라던지 해결 방법 아시는 분 도와주시면 감사하겠습니다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <limits.h>
#define SIZE 100

using namespace std;

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

void bfs(int n, int map[][SIZE], int bound[][SIZE], int initx, int inity, int num);
int dist(int n, int bound[][SIZE], int x, int y, int distan[][SIZE]);

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


	//input size
	int n, i, j;
	int map[SIZE][SIZE] = { 0 };
	int bound[SIZE][SIZE] = { 0 };
	int distan[SIZE][SIZE] = { 0 };
	cin >> n;

	//input map
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}

	int cnt = 0;

	//make island map
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			if (map[i][j] && !bound[i][j]) {
				cnt++;
				bfs(n, map, bound, i, j, cnt);
			}
		}
	}

	int min = INT_MAX;

	//calculate distancd
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			if (bound[i][j] != 0 && bound[i][j] != -1) {
				int dis = dist(n, bound, i, j, distan);
				if (dis) {
					if (dis < min) {
						min = dis;
					}
				}
			}
		}
	}

	cout << min;

}

void bfs(int n, int map[][SIZE], int bound[][SIZE], int initx, int inity, int num) {
	queue<pair<int, int>> q;
	bound[initx][inity] = num;
	q.push({ initx,inity });

	while(!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();

		bool judge = true;
		for (int i = 0; i < 4; i++) {
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];

			if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
				continue;
			}
			if (bound[nx][ny] == num || bound[nx][ny] == -1) {
				continue;
			}
			if (!map[nx][ny]) {
				judge = false;
				continue;
			}
			bound[nx][ny] = num;
			q.push({ nx,ny });
		}
		if (judge) {
			bound[cur.first][cur.second] = -1;
		}
	}
}

int dist(int n, int bound[][SIZE], int x, int y, int distan[][SIZE]) {
	int label = bound[x][y];

	queue<pair<int, int>> q;
	q.push({ x,y });
	distan[x][y] = 0;

	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];

			if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
				continue;
			}
			if (bound[nx][ny] == label || bound[nx][ny] == -1) {
				continue;
			}
			if (bound[nx][ny] != 0) {

				return distan[cur.first][cur.second];
			}
			q.push({ nx,ny });
			distan[nx][ny] = distan[cur.first][cur.second] + 1;
		}
	}
	return 0;
}

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

문제

문제

출처

ICPC

C++ 메모리 초과 해결하는 방법 있나요,,, (14%)

zmxncbv777 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말