cgy12306
[백준 BoJ] 2667 - 단지번호붙이기 본문
// https://www.acmicpc.net/problem/2667
// 단지번호붙이기
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int map[27][27], N, cnt = 0, tcnt = 0;
bool visited[27][27];
vector<int> town;
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
void bfs(int x, int y) {
queue<pair<int, int>> que;
que.push(make_pair(x, y));
while (!que.empty()) {
int x = que.front().first;
int y = que.front().second;
map[y][x] = 0;
que.pop();
tcnt++;
for (int i = 0; i < 4; i++) {
int ax = x + dx[i];
int ay = y + dy[i];
if (ax <= 0 || ay <= 0 || ax > N || ay > N)continue;
if (map[ay][ax] != 1 || visited[ay][ax]) continue;
map[ay][ax] = 0;
visited[ay][ax] = true;
que.push(make_pair(ax, ay));
}
}
town.push_back(tcnt);
tcnt = 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
int num;
num = cin.get();
if (num == '\n') {
num = cin.get();
}
map[i][j] = num - 48;
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (map[i][j] == 1 && !visited[i][j]) {
bfs(j, i);
cnt++;
}
}
}
cout << cnt << "\n";
sort(town.begin(), town.end());
for (int i = 0; i < cnt; i++) {
cout << town[i] << "\n";
}
}
'Algorithm > C++' 카테고리의 다른 글
[백준 BoJ] 4963 - 섬의 개수 (0) | 2021.07.01 |
---|---|
[백준 BoJ] 2583 - 영역 구하기 (0) | 2021.07.01 |
[백준 BoJ] 2178 - 미로 탈출 (0) | 2021.07.01 |
[백준 BoJ] 7569 - 토마토 (0) | 2021.06.30 |
[백준 BoJ] 7576 - 토마토 (0) | 2021.06.30 |
Comments