글 읽기 - 잘 푼 것 같은데 통과가 안되네요 ㅠㅠ.. 도와주세요 !

wldus4498 5년 전 0

bfd로 풀었고 큐의 형태는 queue<pair<vector<char>, int>> 입니다

시간초과라고 뜨긴 하는데 제 코드에 무슨 문제가 있는 걸까요 ?

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <math.h>

using namespace std;
bool isvisit[10000];

void bfs(int, int);

int main() {

	int TC;
	scanf("%d", &TC);

	for (int i = 0; i < TC; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		for (int j = 0; j < 10000; j++) {
			isvisit[j] = false;
		}

		bfs(a, b);
		printf("\n");
	}

}
void bfs(int A, int B) {

	queue<pair<vector<char>, int>> q;
	vector<char> output;
	pair<vector<char>, int> temp = make_pair(output, A);
	q.push(temp);
	
	vector<char> Dtemp, Stemp, Ltemp, Rtemp, Dnum, Snum, Lnum, Rnum; 
	
	while (!q.empty()) {
		temp = q.front();
		q.pop();
		isvisit[temp.second] = true;

		if (B == temp.second) {
			for (int i = 0; i < temp.first.size(); i++) {
				printf("%c", temp.first.at(i));
			}
			return;
		}

		
		int Dnum = (temp.second * 2) % 10000;
	
		int Snum = temp.second - 1;
		if (Snum < 0)
			Snum = 9999;

		
		int NumberOfDigit[4];
		for (int i = 0; i < 4; i++) 
			NumberOfDigit[i] = temp.second / (int)pow(10, i) % 10;
		
		int Lnum = 0, Rnum=0;
		Lnum = NumberOfDigit[3] + NumberOfDigit[0] * 10 + NumberOfDigit[1] * 100 + NumberOfDigit[2] * 1000;
		Rnum = NumberOfDigit[1] + NumberOfDigit[2] * 10 + NumberOfDigit[3] * 100 + NumberOfDigit[0] * 1000;

		if (!isvisit[Dnum]) {
			Dtemp = temp.first;
			Dtemp.push_back('D');
			q.push(make_pair(Dtemp , Dnum));
			isvisit[Dnum] = true;
		}
		if (!isvisit[Snum]) {
			Stemp = temp.first;
			Stemp.push_back('S');
			q.push(make_pair(Stemp, Snum));
			isvisit[Snum] = true;
		}
		if (!isvisit[Lnum]) {
			Ltemp = temp.first;
			Ltemp.push_back('L');
			q.push(make_pair(Ltemp, Lnum));
			isvisit[Lnum] = true;
		}
		if (!isvisit[Rnum]) {
			Rtemp = temp.first;
			Rtemp.push_back('R');
			q.push(make_pair(Rtemp, Rnum));
			isvisit[Rnum] = true;
		}
	}

}

djm03178 5년 전 2

지금까지 지나온 경로를 통째로 큐에 넣으면 매번 전체를 복사해야 하므로 시간이 오래 걸립니다. 지금 문제는 그것도 효율적으로 만들면 통과될 수 있기는 한데, vector<char>는 너무 무겁습니다.

경로 전체를 저장하지 않고 각 수가 어떤 수로부터 어떤 명령에 의해 왔는지만 저장해두고 나중에 목적지에 도달했을 때만 역추적해서 전체 경로를 얻어내는 식으로 하면 빠르게 풀 수 있습니다.

wldus4498 5년 전 0

감사합니다 해결했어요 !

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

문제

문제

출처

ICPC

잘 푼 것 같은데 통과가 안되네요 ㅠㅠ.. 도와주세요 !

wldus4498 5년 전 0

djm03178 5년 전 2

wldus4498 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말