[C++/BFS] 백준 2667 단지 번호 붙이기

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int len;
char map[25][25]; // 실제 지도(0,1)
bool visit[25][25] = { false, }; // 방문 여부 표시
int dir[4][2] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 동서남북 이동
queue<pair<int, int>> q; // 모든 단지의 위치를 담는 큐
 
bool check(int row, int col) {
    // 위치가 지도 범위에서 벗어날 경우 false 리턴
    if (row < 0 || row > len - 1 || col < 0 || col > len - 1) return false;
    // 방문했던 위치인 경우 false 리턴
    if (visit[row][col]) return false;
    // 0, 즉 단지가 아닌 경우 false 리턴
    if (map[row][col] == '0') return false;
    // 이동할 수  있으며 처음 방문하는 단지의 위치이므로 true 리턴
    return true;
}
 
void solve() {
    vector<int> apartment; // 단지별 크기를 담는 벡터
    queue<pair<int, int>> tmp; // 한 단지만의 위치를 담는 큐
 
    while (!q.empty()) {
        pair<int, int> now = q.front();
        q.pop();
        // 이미 방문한 단지일 경우 아래 과정을 진행하지 않는다
        if (visit[now.first][now.second]) continue; 
        visit[now.first][now.second] = true; // 방문표시
        tmp.push(now); // 현재 위치가 새로운 단지의 위치이므로 tmp에 push
        int size = 1;
        while (!tmp.empty()) {
            pair<int, int> now = tmp.front(); // row, col
            tmp.pop();
            for (int i = 0; i < 4; i++) { // 동서남북으로 위치 이동
                while (check(now.first + dir[i][0], now.second + dir[i][1])) {
                    // 동서남북 중 처음 방문하는 같은 단지의 위치를 tmp에 push 함
                    tmp.push({ now.first + dir[i][0], now.second + dir[i][1] });
                    // 방문했다는 표시를 함
                    visit[now.first + dir[i][0]][now.second + dir[i][1]] = true;
                    // 단지 크기 1 증가
                    size++;
                }
            }
        }
        apartment.push_back(size); // 한 단지의 크기를 apartment에 push
    }
 
    sort(apartment.begin(), apartment.end());
    cout << apartment.size() << endl;
    for (int i = 0; i < apartment.size(); i++) // 단지별 크기를 오름차순으로 출력
        cout << apartment[i] << endl;
}
 
int main() {
    cin >> len;
    for (int i = 0; i < len; i++)
        cin >> map[i];
 
    for (int i = 0; i < len; i++) 
        for (int j = 0; j < len; j++)
            if (map[i][j]=='1') q.push({ i,j}); // 단지의 위치를 q에 푸시
 
    solve();
}