글 읽기 - [9019] 시간초과 원인을 찾지 못하겠습니다. 도움 부탁드립니다...

wbjeon2k 5년 전 0

bfs 문제 입니다.

parent[ ] 에 탐색 경로를 남기고, dslr[ ]에 탐색 과정(D,S,L,R)을 저장하고, bfs 탐색이 끝난 이후에 하나씩 추적하여 경로를 출력했습니다.

자료 구조에 문제가 있는건지, 각 DSLR 연산에 해당하는 함수들이 너무 느린건지, 입출력에 문제가 있는건지 생각을 많이 해봤지만

여기에서 어떻게 시간을 더 줄일 수 있을지 잘 생각이 나지 않습니다.

간단한 힌트라도 도움이 될 것 같습니다. 여기 계시는 고수분들의 많은 도움 부탁드립니다 ㅠ

#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>


using namespace std;

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

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

int L(int n){
	int d1,d2,d3,d4;

	d4 = n%10; n = n/10;
	d3 = n%10; n = n/10;
	d2 = n%10; n = n/10;
	d1 = n%10;
	
	return d1 + 10*d4 + 100*d3 + 1000*d2;
}

int R(int n){
	int d1,d2,d3,d4;

	d4 = n%10; n = n/10;
	d3 = n%10; n = n/10;
	d2 = n%10; n = n/10;
	d1 = n%10;
	
	return d3 + 10*d2 + 100*d1 + 1000*d4;
}

int ADJ[10010][4];
int N;

int main(){
	
	scanf("%d",&N);
	
	while(N--){
		int s,e;
		scanf("%d %d",&s,&e);
		
		bool visited[10010] = {false, };
		int parent[10010] = {0, };
		char dslr[10010] = {'Z', };
		queue<int> Q;
		Q.push(s);
		visited[s] = true;
		parent[s] = s;
		dslr[s] = 'X';
		
		while(!Q.empty()){
			int here = Q.front();
			visited[here] = true;
			Q.pop();
			
			int there = D(here);
			if(!visited[there]){
				Q.push(there);
				parent[there] = here;
				dslr[there] = 'D';
			}
			
			there = S(here);
			if(!visited[there]){
				Q.push(there);
				parent[there] = here;
				dslr[there] = 'S';
			}
			
			there = L(here);
			if(!visited[there]){
				Q.push(there);
				parent[there] = here;
				dslr[there] = 'L';
			}
			
			there = R(here);
			if(!visited[there]){
				Q.push(there);
				parent[there] = here;
				dslr[there] = 'R';
			}
			
		}
		
		while(parent[e] != e){
		    printf("%c",dslr[e]);
		    e = parent[e];
		}
		printf("\n");
		
	}
	
	return 0;
}

3587jjh 5년 전 0

큐에서 원소를 꺼냈을때 visited체크를 하시면 이미 큐에 들어있는 원소가 visited된지 모르는 상태이기 때문에 그 원소를 중복해서 큐에 넣어버리는 일이 발생하게 됩니다

큐에 원소를 넣기 전에 visited체크를 하는게 좋을 것 같습니다

wbjeon2k 5년 전 0

@3587jjh 감사합니다! 시도 해 보겠습니다.

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

문제

문제

출처

ICPC

[9019] 시간초과 원인을 찾지 못하겠습니다. 도움 부탁드립니다...

wbjeon2k 5년 전 0

3587jjh 5년 전 0

wbjeon2k 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말