[PS] 백준 2667번 - 단지번호붙이기

BFS를 이용하여 각 단지별로 넓이를 구해 배열에 넣은후 오름차순 정렬하여 출력한다.

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

using namespace std;

int N, a[25][25] = {}, cnt = 0, b[400] = {};
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};

void BFS() {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (a[i][j] == 1) {
        queue<pair<int, int>> q;
        q.push({i, j});
        a[i][j] = 0;
        b[cnt]++;
        while (!q.empty()) {
          int x = q.front().first;
          int y = q.front().second;
          q.pop();
          for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
              if (a[nx][ny] == 1) {
                q.push({nx, ny});
                a[nx][ny] = 0;
                b[cnt]++;
              }
            }
          }
        }
        cnt++;
      }
    }
  }
  sort(b, b+cnt);
  cout << cnt << endl;
  for (int i = 0; i < cnt; i++)
    cout << b[i] << endl;
}

int main(void) {
  cin >> N;
  for (int i = 0; i < N; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < N; j++)
      a[i][j] = s[j] - '0';
  }
  BFS();
}