글 읽기 - 처음보는 런타임에러가있는데 검색해도 무슨말인지 모르겠습니다..

jumpingz 6년 전 0

큐를 이용하여 완전탐색을 하는 방식으로 구현했는데 계속 런타임에러가 나길래 몇개 예제를 넣어보니까

1234 9999 넣는 순간 터지던데 이런 에러가 발생하더라구요..

DEBUG_ERROR("vector<bool> iterator not dereferencable");

검색해보니까 열거형의 마지막으로 접근할때 발생하는 에러라는데 뭔소리인지 모르겠네요..

해당 코드가 왜 저런 에러를 발생시키는지 알 수 있을까요??

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

using namespace std;

struct DATA
{
	int D;
	string str;
	DATA(int D, string str) : D(D), str(str) {}
};

string BFS(vector<bool> &Check, int A, int B);

int main()
{
	int A, B, N;

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		vector<bool> Check(10001, false);
		cin >> A >> B;
		cout << BFS(Check, A, B) << '\n';
	}

	return 0;
}

string BFS(vector<bool> &Check, int A, int B)
{
	queue<DATA> q;

	q.push(DATA(A, ""));

	while (q.empty() != 1)
	{
       		int Dtemp = q.front().D;
 		string Stemp = q.front().str;
		q.pop();

		if (Dtemp == B)
			return Stemp;

		if (Dtemp * 2 > 9999)
		{
			if (Check[(Dtemp * 2) % 10000] == false)
			{
				Check[(Dtemp * 2) % 10000] = true;
				q.push(DATA((Dtemp * 2) % 10000, Stemp + 'D'));
			}
		}
		else
		{
			if (Check[Dtemp * 2] == false)
			{
				Check[Dtemp * 2] = true;
				q.push(DATA((Dtemp * 2), Stemp + 'D'));
			}
		}
			
		if (Dtemp - 1 == 0)
		{
			if (Check[9999] == false)
			{
				Check[9999] = true;
				q.push(DATA(9999, Stemp + 'S'));
			}
		}
			
		else
		{
			if (Check[Dtemp - 1] == false)
			{
				Check[Dtemp - 1] = true;
				q.push(DATA(Dtemp - 1, Stemp + 'S'));
			}
		}
			
		if (Check[((Dtemp % 1000) * 10) + (Dtemp / 1000)] == false)
		{
			Check[((Dtemp % 1000) * 10) + (Dtemp / 1000)] = true;
			q.push(DATA(((Dtemp % 1000) * 10) + (Dtemp / 1000), Stemp + 'L'));
		}

		if (Check[((Dtemp % 10) * 1000) + (Dtemp / 10)] == false)
		{
			Check[((Dtemp % 10) * 1000) + (Dtemp / 10)] = true;
			q.push(DATA(((Dtemp % 10) * 1000) + (Dtemp / 10), Stemp + 'R'));
		}
	}
}

doju 6년 전 0

메시지는 거창하지만 평범하게 잘못된 인덱스를 참조해서 일어나는 오류입니다. S 연산을 하는 부분의 예외 처리에 실수가 있습니다.

jumpingz 6년 전 0

감사합니다.. 입력값에 0이 들어오는게 있엇군요.. 덕분에 해결했습니다만 궁금한점이 하나더 있는데

이런 문제의 BigO 는 어떻게 계산해야하는지 알 수 있을까요?? 막연하게 완전탐색이라고해서 무조건 N! 이런건아닐것같은데요..

알려주실수 있나요?

doju 6년 전 0

일반적인 BFS는 각각의 상태를 한 번씩만 방문하게 되기 때문에 시간복잡도는 O(상태의 개수)가 됩니다. 이 문제의 경우는 상태의 개수가 10000개로 정해져 있다고 볼 수 있습니다.

다만 지금의 구현은 연산 과정을 전부 문자열로 저장하고 있기 때문에 새로운 상태를 방문할 때마다 문자열을 생성 및 복사하게 되고, 이 과정에서 상당한 오버헤드가 발생합니다. 정보를 보다 적게 저장하면서 명령어 나열을 복원할 방법을 생각해 보세요.

jumpingz 6년 전 0

감사합니다

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

문제

문제

출처

ICPC

처음보는 런타임에러가있는데 검색해도 무슨말인지 모르겠습니다..

jumpingz 6년 전 0

doju 6년 전 0

jumpingz 6년 전 0

doju 6년 전 0

jumpingz 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말