[백준] 2267 단지번호붙이기

백준2267

dfs(재귀),bfs를 이용하여 구현해 보았다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> vc;
int N;
int map[25][25];
int visit[25][25] = { 0 };
int dx[] = { -1,1,0,0 }; //좌,우
int dy[] = { 0,0,-1,1 }; //상,하 
int room;


void bfs(int x, int y) {

	queue<pair<int,int>> q;
	q.push(make_pair(x, y));
	visit[x][y] = 1;
	room++;

	//큐가 비어있지 않는 동안
	while (!q.empty()) {
		//큐의 가장 앞에 있는 노드 꺼내기
		x = q.front().first;
		y = q.front().second;
		q.pop();

		//현재 노드에 인접한 모드 노드 탐색
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			//지도를 벗어나지 않고
			if (nx >= 0 && nx < N&&ny >= 0 && ny < N) {
				//집이면서 방문한 적이 없다면 q에 push
				if (map[nx][ny] == 1 && visit[nx][ny] == 0) {
					q.push(make_pair(nx, ny));
					visit[nx][ny] = 1;
					room++;
				}
			}
		}

	}
}

void dfs_recursion(int x, int y) {
	
	visit[x][y] = 1;
	room++;

	//해당 위치의 주변을 확인 (인접 노드 방문)
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		//지도를 벗어나지 않고
		if (nx >= 0 && nx < N&&ny >= 0 && ny < N) {
			//집이면서 방문한 적이 없다면 방문
			if (map[nx][ny] == 1 && visit[nx][ny] == 0) {
				dfs_recursion(nx, ny);
			}
		}
	}
}

int main() {

	scanf("%d", &N); //5<=N<=25
	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&&visit[i][j]==0) {
				room = 0;
				//dfs_recursion(i, j);
				bfs(i, j);
				vc.push_back(room);
			}
		}
	}

	printf("%d\n", vc.size());
	sort(vc.begin(),vc.end());

	for (int i = 0; i < vc.size(); i++) {
		printf("%d\n", vc[i]);
	}

	return 0;
}