단지번호붙이기 / 백준 (Baekjoon) / 2667

---

단지번호붙이기 / 백준 (Baekjoon) / 2667

** 여기서 다루는 알고리즘 문제는 저의 창작 문제가 아닐 경우, 저작권 관련 문제를 방지하고자, 문제의 대략적인 설명 및 요구사항만 소개하고 있습니다. 

** 이 공간에서 공유되는 풀이 및 Source code는 제 개인의 학습 목적이며, 당연히 최선의 정답이 아닙니다. 

** 혹시 더 나은 방법이나 아이디어가 있으신 경우에는, 댓글에 의견을 공유해주시면 감사하겠습니다.

** Source code는 C 언어로 작성되었습니다.

---

알고리즘 분류 및 개요

     - 너비 우선 탐색 (BFS, Breadth First Search)

 

 

Input / output

- 입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

- 출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

 

주의 사항

• 전형적인 BFS 문제인데, 아파트 단지 별로 각 한 번씩 BFS가 수행되어야 하는 부분이 핵심입니다.

• BFS에서는 공통적으로,

1. 방문한 node가 재방문하지 않도록 visit flag를 세워서 queue가 full이 되지 않도록 관리되어야 하고
2. 요구 사항에 특별한 제한이 없을 경우, 네 방향(또는 여덟방향) 으로 모두 node check가 되어야 합니다.

• 마지막 출력 단의 정렬을 위해서, 표준 library에서 제공하는 qsort를 활용하였습니다.

Source code

---

///////////////////////////////////////////////
// - Backjoon 2667 : 단지번호붙이기
// - https://www.acmicpc.net/problem/2667
///////////////////////////////////////////////

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

typedef unsigned int	(u32);
typedef unsigned short  (u16);
typedef unsigned char	(u8);

typedef signed int		(s32);
typedef signed short	(s16);
typedef signed char		(s8);

#define	MAX_INPUT_SIZE	(25)

// -- Global variables

// Input
u32 g_size;
u8 input_buf[MAX_INPUT_SIZE][MAX_INPUT_SIZE];

// BFS - Queue
typedef struct _tag_POSITION {
	u32 pos_x;
	u32 pos_y;
}__POS;

u32 Q_front_flag;
u32 Q_rear_flag;

__POS Queue[MAX_INPUT_SIZE * MAX_INPUT_SIZE];

#define ENQUEUE(x, y, Q_pos)	do { Queue[Q_pos].pos_x = (u32)x; Queue[Q_pos].pos_y = (u32)y; Q_pos++; } while(0)
#define DEQUEUE(x, y, Q_pos)	do { x = Queue[Q_pos].pos_x; y = Queue[Q_pos].pos_y; Q_pos++; } while(0)

// BFS - visit buf
u8 visit_buf[MAX_INPUT_SIZE][MAX_INPUT_SIZE];

// Result
u32 g_total_complex_num;
u32 g_bound_for_next_step;
u16 g_complex_num_list[MAX_INPUT_SIZE * MAX_INPUT_SIZE];

void InitQueueInfo( void )
{
	Q_front_flag = 0;
	Q_rear_flag = 0;
	g_bound_for_next_step = 0;

	memset(Queue, 0, sizeof(__POS) * MAX_INPUT_SIZE * MAX_INPUT_SIZE);
}

static void SetInputBuffer( void )
{
	u32 i, j;

	scanf("%d", &g_size);

	for (i = 0; i < g_size; i++)
	{
		for (j = 0; j < g_size; j++)
		{
			scanf(" %c", &input_buf[i][j]);
		}
	}
}

static __inline u8 CheckUnvisitedNode( s32 pos_x, s32 pos_y )
{
	if ((visit_buf[pos_y][pos_x] == 0) && (input_buf[pos_y][pos_x] == '1'))
	{
		ENQUEUE(pos_x, pos_y, Q_rear_flag);
		visit_buf[pos_y][pos_x] = 1;
		return 1;
	}

	return 0;
}

static void BFS( s32 pos_x, s32 pos_y )
{
	if (pos_y + 1 < g_size)		CheckUnvisitedNode( pos_x, pos_y + 1 );
	if (pos_y >= 1)				CheckUnvisitedNode( pos_x, pos_y - 1 );
	if (pos_x + 1 < g_size)		CheckUnvisitedNode( pos_x + 1, pos_y );
	if (pos_x >= 1)				CheckUnvisitedNode( pos_x - 1, pos_y );
}

// 오름차순
int Compare(const void *first, const void *second)
{
    if (*(u16*)first > *(u16*)second)
        return 1;
    else if (*(u16*)first < *(u16*)second)
        return -1;
    else 
        return 0;
}

s32 main(void)
{
	u32 i, j;
	u32 bound_for_next_step = 0;

	SetInputBuffer();

	for (i = 0; i < g_size; i++)
	{
		for (j = 0; j < g_size; j++)
		{
			if (Q_rear_flag > 0)	InitQueueInfo();

			// (input_buf == '1' && unvisited node)
			if (CheckUnvisitedNode(i, j))
			{
				bound_for_next_step = Q_rear_flag;

				do {
					u32 curr_pos_x, curr_pos_y;

					DEQUEUE(curr_pos_x, curr_pos_y, Q_front_flag);
					BFS(curr_pos_x, curr_pos_y);

					if (Q_front_flag == bound_for_next_step)	
					{
						bound_for_next_step = Q_rear_flag;
					}

				} while (Q_front_flag < Q_rear_flag);

				g_complex_num_list[g_total_complex_num++] = Q_rear_flag;
			}
		}
	}

	//Quick sort @ 
	qsort(g_complex_num_list, g_total_complex_num, sizeof(u16), Compare);

	// Print results
	printf("%d\n", g_total_complex_num);
	for (i = 0; i < g_total_complex_num; i++)
	{
		printf("%d\n", g_complex_num_list[i]);
	}

	return 0;
}

---

난이도 / 중요도 / 재시도

  ★★☆☆☆ / ★★☆☆☆ / x 0

출처 / 관련 링크

- Baekjoon online judge : https://www.acmicpc.net/problem/2667

- BFS Algorithm 소개 : http://jayce-with.tistory.com/9