[알고리즘/문제풀이][BOJ 2667번] 단지번호붙이기

단지번호붙이기 문제는 BFS의 특성을 이용하여 해결할 수 있는 문제입니다. BFS가 연결된 모든 노드를 탐색한다는 특성을 응용한 Flood Fill 기법을 사용하여 해결할 수 있습니다. 

첫 번째 셀부터 마지막 셀까지 순차적으로 탐색하다 단지가 발견되면 그 지점을 루트로 삼아 BFS로 단지를 탐색합니다. 단지가 모든 발견되면 다시 셀을 순차적으로 탐색하며 모든 단지가 발견될 때까지 이를 반복합니다.

작성한 코드는 다음과 같습니다.

#include<stdio.h>
#pragma warning(disable : 4996)
//https://ark-hive.tistory.com/

int N;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

int map[30][30];
int house[30 * 30];
int wp, rp;

int cnt = 1;

struct Queue {
	int x;
	int y;
};

struct Queue queue[2000200];
struct Queue temp;

void enqueue(int x, int y) {
	queue[wp].x = x;
	queue[wp].y = y;
	wp++;
}

struct Queue dequeue() {
	return queue[rp++];
}

int empty() {
	return wp == rp;
}

void sort() {
	int temp1;

	for (int i = 2; i < cnt; i++) {
		for (int j = i + 1; j <= cnt; j++) {
			if (house[i] > house[j]) {
				temp1 = house[i];
				house[i] = house[j];
				house[j] = temp1;
			}
		}
	}
}

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

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%1d", &map[i][j]);
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 1) {
				wp = 0;
				rp = 0;
				cnt++;
				enqueue(j, i);
				map[i][j] = cnt;
				house[cnt]++;

				while (!empty()) {
					temp = dequeue();
					for (int k = 0; k < 4; k++) {
						int nx = temp.x + dx[k];
						int ny = temp.y + dy[k];
						if (nx < 0 || nx >= N) continue;
						if (ny < 0 || ny >= N) continue;
						if (map[ny][nx] != 1) continue;

						enqueue(nx, ny);
						map[ny][nx] = cnt;
						house[cnt]++;
					}
				}
			}
		}
	}

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

	sort();

	for (int i = 2; i <= cnt; i++) {
		printf("%d\n", house[i]);
	}

}

문제의 지문은 다음의 링크에서 확인할 수 있습니다.

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