백준 4963번 : 섬의 개수 C++

BOJ 4963번 섬의개수 문제

BFS로 붙어있는거 체크를 하는데, 2667번 단지번호붙이기와 거의 같은데, 대각선 방향이 추가된다.

2667.cpp

#include <bits/stdc++.h>
using namespace std;
int map_[26][26];
int countCheck[26][26];
int townNum;
int n;
int dirY[4] = {+1, -1, 0, 0};
int dirX[4] = {0, 0, -1, +1};

void BFS(int y, int x, int townNum) {
    queue<pair<int, int> > q;
    q.push({y, x});
    countCheck[y][x] = townNum;
    while (!q.empty()) {
        y = q.front().first;
        x = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nextY = y + dirY[i];
            int nextX = x + dirX[i];
            if (nextY >= 0 && nextY < n && nextX >= 0 && nextX < n) {
                if (map_[nextY][nextX] == 1 && countCheck[nextY][nextX] == 0) {
                    q.push({nextY, nextX});
                    countCheck[nextY][nextX] = townNum;
                }
            }
        }
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &map_[i][j]);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map_[i][j] == 1 && countCheck[i][j] == 0) {
                townNum++;
                BFS(i, j, townNum);
            }
        }
    }
    vector<vector<int> > town(25 * 25);

    for (int y = 0; y < n; y++) {
        for (int x = 0; x < n; x++) {
            int townIndex = countCheck[y][x];
            if (townIndex == 0) continue;
            town[townIndex].push_back(1);
        }
    }
    sort(town.begin(), town.end());

    cout << townNum << '\n';
    for (int i = 0; i < town.size(); i++) {
        if (town[i].size() == 0) continue;
        cout << town[i].size() << '\n';
    }
}