글 읽기 - BFS 큐의 최대 갯수는 왜 10000개일까요?

gkgkehdrms 2년 전 0

안녕하세요 아래 코드를 써서 문제는 통과했습니다.

그런데 풀다 보니 궁금증이 생겨서요

BFS 함수에서 큐를 선언하고 81번 줄에서 Ini_q 함수를 써서 큐를 초기화합니다.

여기서 10001개의 요소를 선언하였는데, 원형 큐를 사용한다면 100개만 선언해도 괜찮지 않나요?

Enque, Deque 함수에서 원형 큐가 되도록 작성했고, 맨 처음 코드에서는 큐의 최대치를 100개만 썼는데

답이 들렸다고 나왔습니다.

10000개가 된다는 말은 시작점부터 미로 배열 모든 요소에 접근이 가능한지 체크해야 한다는건데,

미로는 사실 인접한 요소만 만나게 되고 그렇기 때문에 아무리 많이 들어가도 큐에 100개만 들어갈 것이라고 생각해야 맞지 않나 해서요

실제로 100*100 크기의 미로에, 모든 요소에 1을 넣은 케이스에서 문제없이 돌아가는 걸 확인했습니다.

어떤 반례가 있기 떄문에 큐의 최대 크기를 10000개로 해야 하는지 고수님들 조언 좀 부탁드립니다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#pragma warning(disable:4996)

//미로 구조체
typedef struct {
	int n;
	int maze[102][102];
} Graph;

//좌표 구조체
typedef struct {
	int x;
	int y;
} Coor;

//BFS 큐 구조체
typedef struct
{
	Coor* que;
	int front, rear;
	int num, max;
} Queue;

//각 요소까지 가기 위한 최소 횟수
int check[101][101];

//미로 초기화
void Ini_g(Graph* g)
{
	for (int i = 0; i < 102; i++)
	{
		for (int j = 0; j < 102; j++)
		{
			g->maze[i][j] = 0;
		}
	}
}

//큐 초기화
void Ini_q(Queue* q, int max)
{
	q->que = (Coor*)calloc(max, sizeof(Coor));
	q->num = q->rear = q->front = 0;
	q->max = max;
	return;
}

//큐 요소 삽입
void Enque(Queue* q, int x, int y)
{
	q->num++;
	Coor temp;
	temp.x = x;
	temp.y = y;
		
	q->que[q->rear++]=temp;

	if (q->rear == q->max) q->rear = 0;
	return;
}

//큐 요소 빼기
Coor Deque(Queue* q)
{
	q->num--;
	Coor temp = q->que[q->front++];
	if (q->front == q->max) q->front = 0;
	return temp;
}

int Empty(Queue* q)
{
	return (q->num == 0);
}

int BFS(Graph* g, int row, int col)
{
	Queue q;
	Ini_q(&q, 10001);

	check[1][1] = 1;
	Enque(&q, 1, 1);
    
    //큐가 빌 때까지 반복
	while (!Empty(&q)) 
	{
		Coor temp = Deque(&q);
		int x = temp.x;
		int y = temp.y;
        //큐의 요소를 빼고 동서남북 요소에 대해 BFS
		if (g->maze[x + 1][y] && !check[x + 1][y])
		{
			check[x + 1][y] = check[x][y] + 1;
			Enque(&q, x + 1, y);
		}
		if (g->maze[x - 1][y] && !check[x - 1][y])
		{
			check[x - 1][y] = check[x][y] + 1;
			Enque(&q, x - 1, y);
		}
		if (g->maze[x][y + 1] && !check[x][y + 1])
		{
			check[x][y + 1] = check[x][y] + 1;
			Enque(&q, x, y + 1);
		}
		if (g->maze[x][y - 1] && !check[x][y - 1])
		{
			check[x][y - 1] = check[x][y] + 1;
			Enque(&q, x, y - 1);
		}
	}

	return check[row][col];
}

int main()
{
	Graph g;
	int row, col;
	scanf("%d%d", &row, &col);
	int i, j;

	Ini_g(&g);
	getchar();

	//미로 설정
	for (i = 1; i <= row; i++)
	{
		for (j = 1; j <= col; j++)
		{
			g.maze[i][j] = getchar() - 48;
		}
		getchar();
	}

	printf("%d\n", BFS(&g, row, col));
	
	return 0;
}

palilo 2년 전 2

size 200개로 제출하니까 맞았네요.

제 생각엔 200개가 최대일 것 같아요.

아래처럼 맵이 생겼다면 외길을 따라 맵의 정 중앙으로 간 뒤에 마름모꼴로 사방으로 퍼지겠죠?

그럼 큐의 최대 크기는 마름모의 최대 둘레와 같고, 마름모의 한 변의 길이는 최대 50이니까 200이겠네요.

제출하신 코드에 이 테스트 케이스 넣으니까 큐의 최대 크기는 196이 나오더라구요

/*
10111111111111111...1111
10111111111111111...1111
10111111111111111...1111
10111111111111111...1111
10111111111111111...1111
10111111111111111...1111
10111111111111111...1111
10000000000000000...1111
11111111111111111...1111
00000000000000000...1111
11111111111111111...1111
11111111111111111...1111
11111111111111111...1111
11111111111111111...1111
11111111111111111...1111
*/
#include <bits/stdc++.h>

int main() {
    using namespace std;
    cin.tie(nullptr)->sync_with_stdio(false);
    for (int i = 0; i != 48; ++i) {
        cout << "10" << string(98, '1') << '\n';
    }
    cout << "1" << string(49, '0') << string(50, '1') << '\n';
    cout << string(100, '1') << '\n';
    cout << string(50, '0') << string(50, '1') << '\n';
    for (int i = 51; i != 100; ++i) {
        cout << string(100, '1') << '\n';
    }
}