백준 2668번: 단지 번호 붙이기 (bfs이용+sorting)

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

#include <stdio.h>

int graph[26][26] = { 0, };
int n = 0;
int queue[1000][2] = { 0, };
int cnt = 0;
int town[1000] = { 0, };

void bfs(int v, int w) {
	int front = 0, rear = 0;
	int ans = 1;
	int dx[4] = { -1, 1, 0, 0 };
	int dy[4] = { 0, 0, -1, 1 };

	queue[rear][0] = v;
	queue[rear++][1] = w;
	graph[v][w] = 0;
	
	while (front < rear) {
		int x = queue[front][0];
		int y = queue[front++][1];

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx<1 || ny<1 || nx>n || ny>n)
				continue;

			if (graph[nx][ny] != 1)
				continue;

			graph[nx][ny] = 0;
			queue[rear][0] = nx;
			queue[rear++][1] = ny;
			ans++;
		}
	}
	town[cnt++] = ans;
}

int main() {
	
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%1d", &graph[i][j]);

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (graph[i][j] == 1)
				bfs(i, j);

	printf("%d\n", cnt);

	for (int i = 0; i < cnt; i++) {
		for (int j = i+1; j < cnt; j++) {
			if (town[i] > town[j]) {
				int tmp = town[i];
				town[i] = town[j];
				town[j] = tmp;
			}
		}
	}

	for (int i = 0; i < cnt; i++)
		printf("%d\n", town[i]);

	return 0;
}