글 읽기 - 경로 출력을 어떻게 하나요?

artage7 6년 전 0

일단 맞췄긴 했는데

시간이 무려 5400ms 나 나옵니다..; 푸신거 보니깐 740ms 도 나오던데 차이가 너무 심해서

살펴보니깐 경로를 배열로 출력하는거 같은데 이해가 잘 안되더라구요... ( 사고가 막힌느낌 ..;)

제 알고리즘은 BFS인데 큐에 저장하는 정보를 구조체로 정의했습니다.

구조체에는 DSLR 계산한 숫자와 각각의 BFS 노드마다 지나온 경로를 저장하기 위한 trace 벡터를 저장합니다.

그러니깐 모든 노드에는 계산한 값과 그 노드가 어떤 경로로 오게됬는지 알기 위한 배열을 가집니다.

1

2 3 4

1에서 2, 3, 4 노드를 BFS알고리즘에 따라 집어 넣으면

2번 노드 경로는 1,2

3번 노드 경로는 1,3

4번 노드 경로는 1,4

가 저장되고... 이런식으로 각각 자기 부모로 부터 얻은 위치에 자기 위치를 추가해서 저장하는... 식으로요..

BFS나 DFS 풀때마다 경로 출력하는 문제를 접하게 되는데

항상 이런식으로 풀다보니깐 메모리와 시간이 후달려서 질문드립니다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

const int MAX_LENGHT = 10000;


int T;
int lhs;
int rhs;
int visited[MAX_LENGHT];

struct numInfo
{
	int value;
	vector<char> trace;
};

queue<numInfo> Q;
numInfo result;





void clearQueue( queue<numInfo>& someQueue)
{
	queue<numInfo> empty;
	swap(someQueue, empty);
}

int D(int num)
{
	return (num*2)%10000;
}

int S(int num)
{
	if( num == 0) return 9999;
	return num-1;
}

int L(int num)
{
	int t = num/1000;
	num %=1000;
	return num*10+t;
}

int R(int num)
{
	int t= num%10;
	num /=10;
	return num+(t*1000);
}


void BFS(int num, int wantedValue)
{
	numInfo number;
	number.value = num;
	number.trace.push_back(NULL);
	Q.push( number );

	while(!Q.empty())
	{
		number = Q.front();
		Q.pop();

		numInfo temp;
		temp.value = D(number.value);
		temp.trace = number.trace;
		if( visited[ temp.value ] == 0 )
		{
			visited[ temp.value ] =1;
			temp.trace.push_back('D');
			if( temp.value == wantedValue )
			{
				result = temp;
				break;
			}

			Q.push(temp);
		}

		temp.value = S(number.value);
		temp.trace = number.trace;
		if( visited[ temp.value ] == 0 )
		{
			visited[ temp.value ] =1;
			temp.trace.push_back('S');
			if( temp.value == wantedValue )
			{
				result = temp;
				break;
			}
			Q.push(temp);
		}

		temp.value = L(number.value);
		temp.trace = number.trace;
		if( visited[ temp.value ] == 0 )
		{
			visited[ temp.value ] =1;
			temp.trace.push_back('L');
			if( temp.value == wantedValue )
			{
				result = temp;
				break;
			}
			Q.push(temp);
		}

		temp.value = R(number.value);
		temp.trace = number.trace;
		if( visited[ temp.value ] == 0 )
		{
			visited[ temp.value ] =1;
			temp.trace.push_back('R');
			if( temp.value == wantedValue )
			{
				result = temp;
				break;
			}
			Q.push(temp);
		}


	}

}


int main()
{
	freopen("test.txt","r",stdin);
	scanf("%d", &T);
	for(int t=0; t<T; t++)
	{
		scanf("%d %d", &lhs,&rhs);
		memset(visited,0,sizeof(visited));
		clearQueue(Q);
		BFS( lhs,rhs );
		for( unsigned int i=1; i<result.trace.size(); i++)
		{
			printf("%c",result.trace[i]);
		}
		printf("\n");
	}




	return 0;
}

kdk8361 6년 전 0

값으로 나올 수 있는게 결국 0~9999니까 10000짜리 배열 만들어놓고 BFS 돌리면서 온 길을 저장하는 방식을 사용하니 1152ms 나오네요.

x = 1234

nx = 2341일 때

f[nx] = x

이렇게 저장했습니다.

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