글 읽기 - C언어 시간초과 질문입니다!!!도와주십쇼 고수님들 ㅠㅠ

scv1211 6년 전 0

BFS랍시고 구현해본건데

while문에서 각 move를 하나씩 수행하여 큐에 넣습니다.

- 추가적으로 visited 배열의 move한 인덱스에 부모노드의 값을 저장합니다(visited[ move ? (팝 된 값) ]=팝 된 값)

while문은 큐에서 pop한 데이터가 찾으려는 값과 같으면 탈출하구요

탈출 후에, visited정보를 갖고 역추적 하며 문자를 printArr배열에 역순으로 저장한 후

printArr를 차례대로 출력해줍니다...

도대체 어떻게 해야 시간초과를 줄일 수 있을까요? 도저히 제 머리로는 떠오르질 않네요 ㅠ

#include <stdio.h>
#include <string.h>

typedef int Data;
typedef struct _visitNode{
	char order;
	int before;
	int isVisit;
}VisitNode;

typedef struct _queue{
	int front,rear;
	Data arr[100];
}Queue;

void QueueInit(Queue *pq){
	pq->front=0;
	pq->rear=0;
	memset(pq->arr,0,100*sizeof(Data));
}
int isEmpty(Queue *pq){
	if(pq->front==pq->rear)
		return 1;
	else
		return 0;
}
int nextPos(int idx){
	if(idx>=100)
		return 0;
	else
		return idx+1;
	
}
int isFull(Queue *pq){
	if(nextPos(pq->rear)==pq->front)
		return 1;
	else
		return 0;
}
void push(Queue *pq,Data data){
	if(isFull(pq))
		return ;
	else{
	pq->rear=nextPos(pq->rear);
	pq->arr[pq->rear]=data;
	}
}
Data pop(Queue *pq){
	if(isEmpty(pq))
		return ;
	else{
		pq->front=nextPos(pq->front);
		return pq->arr[pq->front];
	}
}
Data peek(Queue *pq){
	if(isEmpty(pq))
		return ;
	else
		return pq->arr[nextPos(pq->front)];
}
int moveL(int num){		//order L
	int result;
	int div=1000;
	int q=0,r=0;
	while(q==0){
		if(num==0)
			break;
		q=num/div;
		r=num%div;
		div/=10;
	}
	result=r*10+q;
	return result;
}
int moveR(int num){	//order R
	int result;
	int div=10;
	int q=0,r=0;
	if(num!=0){
	q=num/div;
	r=num%div;}
	if(q==0)
		result=num;
	else if(q<10)
		result=r*10+q;
	else if(q<100)
		result=r*100+q;
	else if(q<1000)
		result=r*1000+q;

	return result;
}
int moveS(int num){	//order S
	if(num-1<0)
		return 9999;
	else
		return num-1;
}
int moveD(int num){	//order D
	if(num*2>9999)
		return (num*2)%10000;
	else
		return num*2;

}
VisitNode visited[10000];
char printArr[10000];
int main(){
	int start,end;
	int i,j,t;
	int k;
	Queue queue;
	int temp=-1;
	scanf("%d",&t);
	
	for(i=0;i<t;i++){    //테스트 케이스를 받습니다
		scanf("%d %d",&start,&end);
		memset(visited,0,10000*sizeof(VisitNode));    //각 테스트케이스 마다 visited 배열을 초기화해 줍니다.
		QueueInit(&queue);        //각 테스트케이스마다 큐를 초기화해줍니다.
		push(&queue,start);

		while(temp!=end){
			temp=pop(&queue);    
			if(visited[moveL(temp)].isVisit==0){    //moveL
				visited[moveL(temp)].isVisit=1;
				visited[moveL(temp)].before=temp;
				visited[moveL(temp)].order='L';
				if(moveL(temp)==end) break;
				push(&queue,moveL(temp));
			}
			if(visited[moveR(temp)].isVisit==0){    //moveR
				visited[moveR(temp)].isVisit=1;
				visited[moveR(temp)].before=temp;
				visited[moveR(temp)].order='R';
				if(moveR(temp)==end) break;
				push(&queue,moveR(temp));
			}
			if(visited[moveS(temp)].isVisit==0){    //moveS
				visited[moveS(temp)].isVisit=1;
				visited[moveS(temp)].before=temp;
				visited[moveS(temp)].order='S';
				if(moveS(temp)==end) break;
				push(&queue,moveS(temp));
			}
			if(visited[moveD(temp)].isVisit==0){    //moveD
				visited[moveD(temp)].isVisit=1;
				visited[moveD(temp)].before=temp;
				visited[moveD(temp)].order='D';
				if(moveD(temp)==end) break;
				push(&queue,moveD(temp));
			}
		}
		k=0;
		j=temp;
		while(j!=start){    //역순으로 문자를 저장합니다.
			printArr[k++]=visited[j].order;
			j=visited[j].before;
		}
		for(j=0;j<k;j++){ //순서대로 문자를 출력합니다.
			printf("%c",printArr[j]);
		}
		printf("\n");
	}
return 0;}

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

문제

문제

출처

ICPC

C언어 시간초과 질문입니다!!!도와주십쇼 고수님들 ㅠㅠ

scv1211 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말