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

문제 : 2667

풀이 point

bfs를 통한 탐색을 진행한다.
크기는 다른 vector에 저장을 한 후 정렬해서 출력한다.

풀이 방법

bfs를 구현한다. bfs의 작동 방식을 잘 알고 있다면 단지 수와 단지내 집의 수를 어디서 증가 시켜야할지 알고 있을 것이다.

코드

//백준 2667, 단지번호붙이기

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

#define x first
#define y second

int N;
int grid[30][30];

std::queue<std::pair<int, int>> Q;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

std::vector<int> answer;

void bfs(int i, int j){
    int ans{0};
    grid[i][j] = 0;
    Q.push({i, j});
    ++ans;
    while(!Q.empty()){
        auto curr = Q.front(); Q.pop();
        for(int k{0}; k<4; ++k){
            int nx = curr.x + dx[k];
            int ny = curr.y + dy[k];
            if(nx >= N || nx < 0 || ny >= N || ny <0) continue;
            if(grid[nx][ny] != 1) continue;
            grid[nx][ny] = 0;
            Q.push({nx, ny});
            ++ans;
        }
    }
    answer.push_back(ans);
}

int main (){

    std::cin >> N;
    
    for(int i{0}; i<N; ++i){
        std::string s;
        std::cin >> s;
        for(int j{0}; j<N; ++j){
            grid[i][j] = s[j]-'0';
        }
    }
    
    int num{0};
    for(int i{0}; i<N; ++i){
        for(int j{0}; j<N; ++j){
            if(grid[i][j] == 1){
                bfs(i, j);
                ++num;
            }
        }
    }

    std::sort(answer.begin(), answer.end());
    std::cout << num << '\n';
    for(auto n : answer) std::cout << n << '\n';

    return 0;
}