글 읽기 - 시간초과 이유가 궁금합니다.

qktlf789456 3년 전 0

일부러 빠르게 배열 큐로 진행하였고,

bfs한번으로 왜 시간초과가 날까요 ㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define EMPTY -123456
#define MAXQUEUE 100000

/*
5 3
2 4
3 2
3 5
4 5
*/

struct node
{
	int x, y, count;
};

struct node queue[MAXQUEUE];
int front = 0, rear = 1;

void enqueue(int x, int y, int count)
{
	struct node temp = { x, y, count };

	if (front != rear)		//full
	{
		queue[rear++] = temp;
		rear = rear % MAXQUEUE;
	}

}

struct node dequeue()
{

	struct node return_node = { EMPTY, EMPTY, EMPTY };
	if (((front + 1) % MAXQUEUE) == rear)
	{
		return return_node;
	}

	front = (front + 1) % MAXQUEUE;
	return_node.x = queue[front].x;
	return_node.y = queue[front].y;
	return_node.count = queue[front].count;

	return return_node;

}

int size;
int target_num;

int** target_data;

int from_x, from_y;

int** visited;

void bfs(int current_x, int current_y, int count)		//현재x, y, 이동횟수;
{
	enqueue(current_x, current_y, count);

	int a[8] = { -2, -2, -1, -1, 1, 1, 2, 2 };
	int b[8] = { -1, 1 ,-2, 2, -2, 2 , -1, 1 };

	struct node current = { EMPTY, EMPTY, EMPTY };
	while ((current = dequeue()).x != EMPTY)
	{

		int current_x = current.x;
		int current_y = current.y;
		int next_count = current.count + 1;

		visited[current_x][current_y] = current.count;

		int next_x, next_y;
		for (int i = 0; i < 8; i++)
		{
			next_x = current_x + a[i];
			next_y = current_y + b[i];

			if (0 <= next_x && next_x < size && 0 <= next_y && next_y < size)
			{
				if(visited[next_x][next_y] == -1)
					enqueue(next_x, next_y, next_count);
			}

		}
		
	}

}

int main()
{
	scanf("%d", &size);

	visited = (int**)malloc(sizeof(int*) * size);

	for (int i = 0; i < size; i++)
	{
		visited[i] = (int*)malloc(sizeof(int) * size);

		for (int j = 0; j < size; j++)
			visited[i][j] = -1;
	}

	scanf("%d", &target_num);

	scanf("%d", &from_x);
	scanf("%d", &from_y);

	from_x--;
	from_y--;

	target_data = (int**)malloc(sizeof(int*) * target_num);

	bfs(from_x, from_y, 0);		//현재x, y, 이동횟수;

	for (int i = 0; i < target_num; i++)
	{
		target_data[i] = (int*)malloc(sizeof(int) * 2);

		scanf("%d", &target_data[i][0]);
		scanf("%d", &target_data[i][1]);

		target_data[i][0]--;
		target_data[i][1]--;
	}

	for (int i = 0; i < target_num; i++)
		printf("%d ", visited[target_data[i][0]][target_data[i][1]]);

	return 0;
}

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

문제

문제

출처

ICPC

시간초과 이유가 궁금합니다.

qktlf789456 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말