글 읽기 - 메모리 초과가 나는 이유를 잘 모르겠습니다.ㅜㅜ

meumang 3년 전 0

큐를 사용하여 bfs로 확인하는 방식으로 코드를 제작했는데,

계속 12%부분에서 메모리초과가 뜹니다..ㅠㅠㅠ

이전 게시판들 참조하면서 수정했는데도 계속 메모리초과가 뜨는데 뭐가 문제인지 잘 모르겠습니다 ㅜㅜ

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int sq[4][2] = { {0,1},{1,0}, {-1,0}, {0,-1} };
int maxi;
vector<vector<char>>v;
bool** visit;
void bfs(int ro, int col, int st_x, int st_y) {
	queue<pair<int, int>> q;
	queue<int>num;
	
	q.push(make_pair(st_x, st_y));
	visit[st_y][st_x] = true;
	num.push(0);

	int result = 0;

	while (!q.empty()) {
		int x = q.front().first; int y = q.front().second; result = num.front();
		q.pop();
		num.pop();
		for (int i = 0; i < 4; i++) {
			int newx = x + sq[i][0], newy = y + sq[i][1];
			if (newx > -1 && newy > -1 && newx < col && newy < ro && visit[newy][newx] ==false && v[newy][newx]=='L') {
				q.push(make_pair(newx, newy));
				num.push(result + 1);
				visit[y][x] = true;
			}
		}	
	}
	if (result > maxi) maxi = result;
}

int main(void)
{
	int col, ro;
	cin >> ro >> col;
	visit = new bool* [ro + 1];

	for (int i = 0; i < ro; i++){
		char ch;
		v.push_back(vector<char>());
		visit[i] = new bool[col + 1];
		for (int j = 0; j < col; j++) {
			cin >> ch;
			v.at(i).push_back(ch);
		}
	}

	for (int i = 0; i < ro; i++)
		fill(visit[i], visit[i] + col, false);

	for (int i = 0; i < ro; i++) {
		for (int j = 0; j < col; j++) {
			if (v[i][j] == 'L') {
				bfs(ro, col, j, i);
				//cout << i << " " << j << endl;
			}
			for (int k = 0; k < ro; k++)
				fill(visit[k], visit[k] + col, false);
		}
	}
	cout << maxi;
	return 0;
}

kms9937 3년 전 0

방문 체크를 할때 visit[y][x]가 아니라 visit[newy][newx]라고 해 주셔야 합니다.

그리고 num에 push 하는것 때문에 메모리초과가 날 수 있을 것 같습니다.

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

문제

문제

출처

ICPC

메모리 초과가 나는 이유를 잘 모르겠습니다.ㅜㅜ

meumang 3년 전 0

kms9937 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말