글 읽기 - 메모리 초과 문제입니다!!

luck 5년 전 0

메모리 초과가 나왔습니다.

아래 코드에서 어떤 부분에서 메모리 부분을 많이 쓰는지 모르겠네요 ㅠㅠ

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#include <string>

using namespace std;


char a[3][3];

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

string ans = "123456780";
bool v[999999999];

typedef struct{
	int x, y;
	string s;
	int num;
}S;
queue<S>q;
int answer;

void change_i(string s){
	int num = -1;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			a[i][j] = s[++num];
}

string change_s(){
	string cs="";
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			cs += a[i][j];
	return cs;
}

void bfs(){
	while (!q.empty()){
		int x = q.front().x;
		int y = q.front().y;
		string s = q.front().s;
		int num = q.front().num;
		q.pop();

		//cout << s << endl;
	
		if (s == ans){
			answer = num;
			return;
		}

		change_i(s);

		for (int k = 0; k < 4; k++){
			int nx = x + dx[k];
			int ny = y + dy[k];

			if (0 <= nx && nx < 3 && 0 <= ny && ny < 3){
				change_i(s);
				a[x][y] = a[nx][ny];
				a[nx][ny] = '0';
				string ts = change_s();
				int tx = stoi(ts);
				if (v[tx] == false){
					v[tx] = true;
					q.push({ nx, ny, ts, num+1});
				}
			}
		}

	}
}

int main(){
	int ansX = 0; int ansY = 0;
	string s = "";
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++){
			cin >> a[i][j];
			s += a[i][j];
			if (a[i][j] == '0'){
				ansX = i;
				ansY = j;
			}
		}

	v[stoi(s)] = true;
	q.push({ ansX, ansY, s, 0 });
	bfs();

	if (answer == 0)
		cout << -1<<endl;
	else
		cout << answer << endl;

	return 0;
}

kyo20111 5년 전 1

문제의 제한을 보면 메모리제한이 32MB인데, bool 형을 10억개 선언하면 메모리를 얼마나 쓸까요?

kyo20111 5년 전 1

32MB = 32 * 1024 * 1024 Byte = 32 * 1024 * 1024 * 8 bit 이므로 계산하면 268,435,456개의 bool 형을 선언 할 수 있겠지만 다른 요소들을 생각하면 그 미만이라고 할 수 있겠네요

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

문제

문제

출처

ICPC

메모리 초과 문제입니다!!

luck 5년 전 0

kyo20111 5년 전 1

kyo20111 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말