글 읽기 - 2583번 영역구하기, C언어 BFS로 구현했는데 왜 틀렸는지 모르겠습니다 ㅠㅠ

kakama 6년 전 0

map 배열에 입력받고

직사각형 없는 부분에 대해서 BFS로 영역 크기를 구해서 sizelist[]에 담아 두었다가

BFS가 모두 끝나면 sizelist를 퀵 정렬로 정렬해서 출력하는 방법을 사용했는데 왜 틀렸다고 나오는지 모르겠네요..

영역의 개수는 cnt로 나타내었습니다.

주석 처리한 부분은 디버깅하면서 넣었던 부분입니다. 제출할 때는 모두 주석처리해서 넣었어요!

예시로 나온 케이스도 잘 출력하고, 여러 예시들 넣었을 때도 제대로 작동하는데 왜 틀렸다고 나오는지 모르겠습니다 ㅠㅠ

도와주세요!!

#include <stdio.h>

int map[101][101] = { 0 };
int cnt = 0;
int xlist[10500], ylist[10500];
int sizelist[1000] = { 0 };
int sizerear = 0;
int front = 0, rear = 0, size = 0;
int M, N;

void quick(int arr[], int left, int right)
{
	int i = left, j = right;
	int temp;
	int pivot = arr[(left + right) / 2];

	do {
		while (arr[i] < pivot) i++;
		while (arr[j] > pivot) j--;

		if (i <= j)
		{
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i++;
			j--;
		}

	} while (i <= j);

	if (left < j) quick(arr, left, j);
	if (i < right) quick(arr, i, right);
}


void enqueue(int _x, int _y)
{
	xlist[rear] = _x;
	ylist[rear] = _y;
	rear++;
	map[_y][_x] = 1;
	size++;
}


void BFS(int x, int y)
{
	size = 0;
	front = 0;
	rear = 0;
	enqueue(x, y);
	while (front < rear)
	{
//		printf("%d %d\n", xlist[front], ylist[front]);
		if (ylist[front] - 1 >= 0 && map[ylist[front] - 1][xlist[front]] == 0)
			enqueue(xlist[front], ylist[front] - 1);
		if (ylist[front] + 1 < M && map[ylist[front] + 1][xlist[front]] == 0)
			enqueue(xlist[front], ylist[front] + 1);
		if (xlist[front] - 1 >= 0 && map[ylist[front]][xlist[front] - 1] == 0)
			enqueue(xlist[front] - 1, ylist[front]);
		if (xlist[front] + 1 < M && map[ylist[front]][xlist[front] + 1] == 0)
			enqueue(xlist[front] + 1, ylist[front]);

		front++;
	}

	sizelist[sizerear++] = size;
}


int main()
{
	int K;
	int i, x, y;
	int x1, y1, x2, y2;
	scanf("%d %d %d", &M, &N, &K);
	for (i = 0; i < K; i++)
	{
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		for (y = y1; y < y2; y++)
			for (x = x1; x < x2; x++)
				map[y][x] = 1;
	}


/*  
	for (y = 0; y < M; y++)
	{
		for (x = 0; x < N; x++)
		{
			printf("%d", map[y][x]);
		}
		printf("\n");
	}
*/
	

	for (y = 0; y < M; y++)
	{
		for (x = 0; x < N; x++)
		{
			if (map[y][x] == 0)
			{
//				printf("%d %d\n", x, y);
				cnt++;
				BFS(x, y);
			}
		}
	}

	
	printf("%d\n", cnt);
	quick(sizelist, 0, sizerear - 1);
	for (i = 0; i < sizerear; i++)
		printf("%d ", sizelist[i]);


	return 0;
}

kakama 6년 전 0

단순히

if (xlist[front] + 1 < M && map[ylist[front]][xlist[front] + 1] == 0)

에서 < M이 아니라 <N인 문제였습니다 ㅠㅠ

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

문제

문제

출처

ICPC

2583번 영역구하기, C언어 BFS로 구현했는데 왜 틀렸는지 모르겠습니다 ㅠㅠ

kakama 6년 전 0

kakama 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말