[Baekjoon/C++] 2667번 단지번호붙이기

문제 설명

입출력 예

코드 구현

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int N;
vector<vector<int>> map;
vector<vector<bool>> visited;

//상하좌우
int dx[4]={-1, 1, 0, 0};
int dy[4]={0, 0, -1, 1};

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

    while(!q.empty()){
        x = q.front().first;
        y = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];

            if(nx>=0 && nx<N && ny>=0 && ny<N && map[nx][ny]==1 && !visited[nx][ny]){
                q.emplace(nx, ny);
                visited[nx][ny]=true;
                houseNum++;
            }
        }
    } 
    return houseNum;  
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    map.resize(N, vector<int>(N));
    visited.resize(N, vector<bool>(N, false));
    vector<int> houses;
    int town=0;

    for(int i=0; i<N; i++){
        string line;
        cin >> line;
        for(int j=0; j<N; j++){
            map[i][j] = line[j]-'0'; //문자 정수로 변환
        }
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(map[i][j]==1 && !visited[i][j]){
                houses.push_back(bfs(i, j));
                town++;
            }
        }
    }

    sort(houses.begin(), houses.end());

    cout << town << "\n";
    for(int h : houses){
        cout << h << "\n";
    }

    return 0;
}

유사한 문제로 1012번이 있다.

---

출처: 백준, https://www.acmicpc.net/problem/2667