글 읽기 - 런타임 에러 문제.. 코드랑 설명도 달았습니다..도와주세요!

his130 6년 전 0

일단 크게 BFS를 사용해서 문제를 풀었습니다.

그 과정에서 상태 하나하나를 배열로 표현하려고 했습니다.

1 2 3

4 5 6

7 8 0

같은 경우 123456780으로 표현하고 string 으로 바꾼후 다시 int형으로 변환하였습니다.

그리고 bfs에서 visit 배열의 경우에 최대 876543210 이지만 이는 너무 커서

87654321 까지로 나타냈습니다. 즉 끝에 자리 하나는 없애서 배열을 만든거죠...

근데 이게 visual 에서는 돌아가는건지, 정답 코드를 올리면 런타임 에러가 출력됩니다.

혹시 이부분이 아닌 다른 문제가 있는건지 잘 모르겠네요..

좀 도와주세요..

#include<iostream>
#include<queue>
#include<string>
#include<string.h>
using namespace std;

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int map[3][3];
int dist[87654321];
string transString(int tmp[][3])
{
	string ret = "";

	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			ret += tmp[i][j] + '0';
		}
	}

	return ret;
}
string makeMap(string c,int x,int y,int nx,int ny)
{
	int m[3][3];
	int cnt = 0;
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			m[i][j] = c[cnt++]-'0';
		}
	}

	swap(m[x][y], m[nx][ny]);

	return transString(m);
}

int main()
{
	int x0, y0, goal = 12345678;
	memset(dist, -1, sizeof(dist));
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 0)
			{
				x0 = i;
				y0 = j;
			}
		}
	}
	
	queue<pair<pair<int,int>,string>> q;
	q.push(make_pair(make_pair(x0,y0), transString(map)));
	dist[stoi(transString(map).substr(0,8))] = 0;

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

		if (stoi(c.substr(0, 8)) == goal)
		{
			break;
		}

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

			if (nx >= 0 && ny >= 0 && nx < 3 && ny < 3)
			{
				string nc = makeMap(c, x, y, nx, ny);

				if (dist[stoi(nc.substr(0, 8))] == -1)
				{
					dist[stoi(nc.substr(0, 8))] = dist[stoi(c.substr(0, 8))] + 1;
					q.push(make_pair(make_pair(nx, ny), nc));
				}
			}
		}

	}
	cout << dist[goal] << endl;

	return 0;
}

godmoon00 6년 전 1

int dist[87654321]; 는 대략 334MB 입니다 문제의 메모리 제한은 16MB 이므로 다른 알고리즘을 이용하셔야 합니다.

his130 6년 전 0

아 그렇군요..

혹시 메모리 계산하는 방법은 어떻게 하신건지 알려주실 수 있나요??

chogahui05 6년 전 1

대략적으로 1M = 100만 byte라고 생각하시면 편합니다. (정확히는 1048576byte = 1M이긴 한데..)

87654321 = 대충 87M (87 * 100만)

int 1개당 4byte라면 328M

state가 생각보다 그렇게 많이 나타나진 않아요.

his130 6년 전 0

가르쳐주셔서 감사합니다!

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

문제

문제

출처

ICPC

런타임 에러 문제.. 코드랑 설명도 달았습니다..도와주세요!

his130 6년 전 0

godmoon00 6년 전 1

his130 6년 전 0

chogahui05 6년 전 1

his130 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말