글 읽기 - [C] 9019 DSLR 시간초과

ramtk6726 4년 전 0

C로 구현한 DSLR입니다.

찾아보니 다른 분들이 C++로 구현한 DSLR과

벡터 대신 구조체 배열로 큐를 만들어서 구현한 부분을 제외하고는 동일합니다.

어느부분에서 시간초과가 나는걸까요? 엄청 느리게 돌아가긴 하네요ㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 10000
#define FALSE 0
#define TRUE 1

typedef struct node {
	int cur_num;
	char command[MAX_SIZE];
} node;
node queue[MAX_SIZE];

int visited[MAX_SIZE];
int A, B, front = -1, rear = -1;
char answer[MAX_SIZE];

void init_arr() {
	front = rear = -1;
	for (int i = 0; i < MAX_SIZE; i++)
		visited[i] = FALSE;
}

int D(int a) {
	return (2 * a) % 10000;
}
int S(int a) {
	if (a == 0)	return 9999;
	else return a - 1;
}

int L(int a) {
	return (a % 1000) * 10 + (a / 1000);
}

int R(int a) {
	return (a % 10) * 1000 + (a / 10);
}

void push(int x, char *command) {
	node temp;
	temp.cur_num = x;
	strcpy(temp.command, command);
	queue[++rear] = temp;
}

node pop() {
	node temp = queue[++front];
	return temp;
}

void bfs() {
	node temp;
	int next_num = A;	
	char str[MAX_SIZE];
	visited[A] = TRUE;
	push(A, "");
	while (front != rear) {
		temp = pop();
		if (temp.cur_num == B) {
			strcpy(answer, temp.command);
			return;
		}

		next_num = D(temp.cur_num);
		if (!visited[next_num]) {
			visited[next_num] = TRUE;
			strcpy(str, temp.command);
			strcat(str, "D");
			push(next_num, str);
		}
		
		next_num = S(temp.cur_num);
		if (!visited[next_num]) {
			visited[next_num] = TRUE;
			strcpy(str, temp.command);
			strcat(str, "S");
			push(next_num, str);
		}

		next_num = L(temp.cur_num);
		if (!visited[next_num]) {
			visited[next_num] = TRUE;
			strcpy(str, temp.command);
			strcat(str, "L");
			push(next_num, str);
		}

		next_num = R(temp.cur_num);
		if (!visited[next_num]) {
			visited[next_num] = TRUE;
			strcpy(str, temp.command);
			strcat(str, "R");
			push(next_num, str);
		}
	}
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d", &A, &B);
		init_arr();
		bfs();
		printf("%s\n", answer);
	}
	return 0;
}

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

문제

문제

출처

ICPC

[C] 9019 DSLR 시간초과

ramtk6726 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말