글 읽기 - 시간초과...c++

um1129 2년 전 0

3%에서 시간초과가 납니다... 어디를 고쳐야 할지 감이 안잡히네요.... 도와주세요 ㅠ ㅠ

#include <queue>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;

int check[10001];
int aa,bb;
int n;
struct node{
	int num; 
	string st;
	node(int a, string s){
		num=a;
		st =s;
	}
};

void BFS( int nn , string s ){
	
	queue<node> q;
	q.push(node(nn,s));
	check[nn]=1;
	
	while(!q.empty()){
		int t_n = q.front().num;
		string t_s = q.front().st;
		q.pop();
		
		if(t_n ==bb){
			cout<<t_s<<'\n';
			break;
		}
		
		if(t_n!=0){
			//D
			if(t_n*2>=10000){
				if(check[(t_n*2)%10000]==0){
					check[(t_n*2)%10000]=1;
					q.push(node((t_n*2)%10000,t_s+"D"));
				}
			}
			else if(t_n*2<10000){
				if(check[t_n*2]==0){
					check[t_n*2]=1;
					q.push(node(t_n*2,t_s+"D"));
				}
			}
			//S
			if(check[t_n-1]==0){ 
				check[t_n-1]=1;
				q.push(node(t_n-1,t_s+"S"));
			}	
			
			//칸채우기 
			string s_tmp = to_string(t_n);
			for(int i=s_tmp.size();i<=3;i++){
				s_tmp="0"+s_tmp; //문자열  
			}	
			//L
			char ch = s_tmp[0]; 
			for(int i= 0 ;i <3;i++){
				s_tmp[i]=s_tmp[i+1];
			} 
			s_tmp[3]=ch;
			int i_tmp = stoi(s_tmp);
			if(check[i_tmp]==0){
				check[i_tmp]=1;
				q.push(node(i_tmp,t_s+"L"));
			}
			//R
			s_tmp = to_string(t_n);
			for(int i=s_tmp.size();i<=3;i++){
				s_tmp="0"+s_tmp;
			}
			ch = s_tmp[3];
			for(int i= 3 ;i >0;i--){
				s_tmp[i]=s_tmp[i-1];
			}
			s_tmp[0]=ch;
			i_tmp = stoi(s_tmp);
			if(check[i_tmp]==0){
				check[i_tmp]=1;
				q.push(node(i_tmp,t_s+"R"));
			}
			
					
		}
		//S
		if(t_n==0){
			if(check[9999]==0){
				check[9999]=1;
				q.push(node(9999,t_s+"S"));
			}
		}

	}
}

int main(void){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);	

	cin>>n;
	
	while(n--){
		cin>>aa>>bb;
		memset(check,0,sizeof(check));
		BFS(aa,"");
	}
}

sunghyeck17 2년 전 1

std::string 관련 메서드들이 은근 느립니다.

DSLR 각각을 구현하는데는 굳이 string을 쓰지 않아도 되는 것들이 있습니다. 그 부분을 string 메서드 대신에 다른 방법으로 바꿔보세요.

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

문제

문제

출처

ICPC

시간초과...c++

um1129 2년 전 0

sunghyeck17 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말