백준 2667 단지번호붙이기

 

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

 

2667번: 단지번호붙이기

 

 

서론

 

BFS를 이용하여 풀이

 

아이디어

 

좌표 (1,1)부터 (n,n)까지 모든 좌표에서 1이고 방문하지 않았으면 BFS를 실행

만약 단지 결과가 3개라면 BFS는 3번 실행되게 된다.

BFS에서는 이동가능한 좌표 한칸씩 이동할때마다 집을 +1하고 방문처리

BFS에서 나올때 카운트된 집을 리턴하고 하나의 단지가 완성된다.

카운트된 집은 배열에 집어넣고

모든 집을 방문했으면 배열을 오름차순 정리 후 BFS 실행 횟수와 함께 배열 출력

 

구현

 

//c++

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

using namespace std;

int map[25][25];
int visit[25][25];
int n;

void input() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		char tmp[26];
		cin >> tmp;
		for (int j = 0; j < n; j++) {
			map[i][j] = tmp[j] - '0';
		}
	}
}

int bfs(int y, int x) {
	queue<pair<int, int>>q;
	int dy[4] = { 0,0,-1,1 };
	int dx[4] = { -1,1,0,0 };
	int cnt = 1;

	visit[y][x] = 1;
	q.push({ y, x });
	while (!q.empty()) {
		y = q.front().first;
		x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int yy = y + dy[i];
			int xx = x + dx[i];
			if (yy >= 0 && xx >= 0 && yy < n && xx < n && map[yy][xx] == 1 && visit[yy][xx] == 0) {
				q.push({ yy,xx });
				visit[yy][xx] = 1;
				cnt++;
			}
		}
	}
	return cnt;
}

int main() {
	vector<int>v;
	int vSize = 0;
	int num = 0;
	input();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (visit[i][j] == 0 && map[i][j] == 1) {
				v.push_back(bfs(i, j));
				num++;
			}
		}
	}
	cout << num << endl;
	sort(v.begin(), v.end());
	vSize = v.size();
	for (int i = 0; i < vSize; i++) {
		cout << v[i] << endl;
	}
}