백준 #2667 [c++]

문제

 

// 풀이

 

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

using namespace std;

bool visited[25][25] = { false };
int map[25][25];

// 상하좌우
int dir_x[] = { 0,0,-1,1 };
int dir_y[] = { 1,-1,0,0 };

int n = 0; // 지도의 크기

int bfs(int y, int x) {
queue<pair<int, int>> q;
q.push(make_pair(y, x));
visited[y][x] = true;

int count = 1; // 이미 1인 노드를 선택했으므로 count는 1부터 시작, 단지의 집 갯수


// 큐가 빌 때 까지
while (!q.empty()) {
auto node = q.front();
q.pop();

for (int i = 0; i < 4; i++) {
int next_x = node.second + dir_x[i];
int next_y = node.first + dir_y[i];

// 범위를 벗어나지 않으며
if (next_x >= 0 && next_y >= 0 && next_x < n && next_y < n) {
// next 지점의 map의 값이 1이고, 아직 방문하지 않았다면
if (map[next_y][next_x] == 1 && visited[next_y][next_x] == false) {
// 방문표시하고 갯수 늘리고 다음 노드를 큐에 push
visited[next_y][next_x] = true;
count++;
q.push(make_pair(next_y, next_x));
}
}
}
}

return count;
}


int main() {

cin >> n;

vector<int> result; // 최대 생길수 있는 단지수 n^2+1
int k = 0; // 단지의 index

// 지도 입력
for (int i = 0; i < n; i++) {
string temp;
cin >> temp;
for (int j = 0; j < n; j++) {
map[i][j] = temp[j] - '0';
}
}

// 방문한 노드인지 확인
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// map에 저장된 값이 1이고 아직 방문하지 않았다면
if (map[i][j] == 1 && visited[i][j] == false) {
result.push_back(bfs(i, j));
k++;
}
else visited[i][j] = true;
}
}

cout << k << endl;
sort(result.begin(), result.end()); // 오름차순 정렬
for (int i = 0; i < k; i++)
cout << result[i] << endl;

return 0;
}