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

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

2667번: 단지번호붙이기

해당 문제는 0과 1로 이루어진 격자판이 주어지며 해당 격자판의 1은 집을 의미하고 0은 빈 집을 의미한다. 이때 집들의 모임인 단지를 정하고 단지의 개수와 각 단지마다 포함 된 집의 개수를 오름차순으로 출력하는 문제이다. 

단지는 상하좌우로 인접한 집들의 집합이다.

 

풀이 :

2 중 for를 사용하여 격자판을 모두탐색 하며 만약 처음 방문하는 집일 경우에 BFS를 통한 상하좌우 방향의 집 탐색을 진행한다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;
struct Node{
	int y, x;
};

int n;
int visit[26][26];
string map[26];
int checkY[4] = { 0, 0, 1, -1 };
int checkX[4] = { 1, -1, 0, 0 };
vector<int> houseList;

int bfs(int y, int x){
	int cnt = 0;
	visit[y][x] = 1;
	queue<Node> qu;
	qu.push({ y, x });

	while (!qu.empty()){
		++cnt;
		Node now = qu.front();
		for (int i = 0; i < 4; ++i){
			int dy = now.y + checkY[i];
			int dx = now.x + checkX[i];
			if (dy < 0 || dx < 0 || dy >= n || dx >= n)continue;
			if (visit[dy][dx] == 0 && map[dy][dx] == '1') {
				qu.push({ dy, dx });
				visit[dy][dx] = 1;
			}
		}
		qu.pop();
	}
	return cnt;
}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n;

	for (int i = 0; i < n; ++i){
		cin >> map[i];
	}

	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			if (visit[i][j] == 0 && map[i][j] == '1'){
				houseList.push_back(bfs(i, j));
			}
		}
	}

	sort(houseList.begin(), houseList.end());
	cout << houseList.size() << endl;
	for (int i = 0; i < houseList.size(); ++i){
		cout << houseList[i] << endl;
	}



}