글 읽기 - 메모리초과.. 원인을 모르겠어요 ㅜ!

ksm9660 6년 전 0

메모리 초과는 겪는 오류인데,

queue 를 쓰다 보면 나중에 가지가 많이 쳐졌을때

큐가 너무 커져서 메모리 초과가 나는 건가요?

제가 queue에다 구조체를 넣었는데, 구조체가 short 변수 3개를 가져서 총 6바이트거든요 ;;

한번만 확인해주세요ㅜ!!!

#include <queue>
#include <iostream>
using namespace std;
typedef struct node{
	short r;
	short c;
	short count;
}Node;
int main(){
	queue<Node> q;
	
	// 입력
	Node start = { 0, 0, 0 };
	int N, M;
	cin >> N >> M;

	// 입력 초기화
	char tempStr[100];
	int **map = new int*[N];
	int **output = new int*[N];
	for (int i = 0; i < N; i++){
		map[i] = new int[M];
		output[i] = new int[M];
		cin >> tempStr;
		for (int j = 0; j < M; j++){
			map[i][j] = tempStr[j] - 48;
			output[i][j] = 0;
		}
	}
	
	// BFS 
	q.push(start);
	while (!q.empty()){
		Node tempNode = q.front();
		q.pop();
		tempNode.count++;
		output[tempNode.r][tempNode.c] = tempNode.count;

		int dr[4] = { 0, -1, 0, 1 };
		int dc[4] = { -1, 0, 1, 0 };

		for (int i = 0; i < 4; i++){
			int r = tempNode.r + dr[i];
			int c = tempNode.c + dc[i];
			Node tempNode2 = { r, c, tempNode.count };

			// 잘리는 조건
			if (r < 0 || N <= r || c < 0 || M <= c || output[r][c] != 0)
				continue;
			if (map[r][c] == 1)
				q.push(tempNode2);
		}
	}

	// 결과
	cout << output[N - 1][M - 1] << endl;
}

indioindio 6년 전 1

큐에 이미 방문한 노드가가 계속 추가되는 것 같네요

ksm9660 6년 전 0

잘리는 조건 보시면,

if (r < 0 || N <= r || c < 0 || M <= c || output[r][c] != 0)

output 배열을 다 0으로 초기화하고

끝에 output[r][r]!=0 에서 한번 방문했던곳은 안가게 해서

간곳은 안가는걸로 알고 있는데...

음....

일단 큐가 커지면서 메모리가 초과된다는 거군요.. 감사합니다!

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

문제

문제

출처

ICPC

메모리초과.. 원인을 모르겠어요 ㅜ!

ksm9660 6년 전 0

indioindio 6년 전 1

ksm9660 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말