Algorithm/BOJ
[BOJ 2667] 단지번호붙이기 C++
surimi🍥
2023. 3. 8. 11:40
반응형
난이도: Silver 1
번호: 2667
생성일: March 8, 2023 11:39 AM
알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색
언어: C++
C++
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int N;
char map[27][27];
bool visit[27][27];
const int dX[] = {0, 0, -1, 1};
const int dY[] = {-1, 1, 0, 0};
int BFS(int i, int j)
{
queue<pair<int, int>> Q;
int cnt = 1;
Q.push({i, j});
visit[i][j] = true;
while (!Q.empty())
{
auto cur = Q.front();
Q.pop();
for (int k = 0; k < 4; k++)
{
int x = dX[k] + cur.first;
int y = dY[k] + cur.second;
if (visit[x][y] || map[x][y] != '1')
continue;
Q.push({x, y});
visit[x][y] = true;
cnt++;
}
}
return (cnt);
}
int main(void)
{
vector<int> complex;
scanf("%d", &N);
for (int i = 1; i <= N; i++)
scanf("%s", &map[i][1]);
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
if (map[i][j] == '1' && !visit[i][j])
complex.push_back(BFS(i, j));
sort(complex.begin(), complex.end());
printf("%lu\n", complex.size());
for (int i : complex)
printf("%d\n", i);
return (0);
}
반응형