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

문제: www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

 

문제풀이

 

각 영역의 넓이를 구하여 오름차순으로 출력하는 문제이다.

 

BFS를 이용하여 각 구역에 대하여 탐색하고 그 넓이를 각각 벡터에 저장하였다.

 

벡터를 sort() 함수를 이용해 오름차순 정렬시킨 후 출력하였다.

 

코드

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

using namespace std;

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int visited[25][25] = {0,};
string board[25];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int n;
    cin>>n;

    for(int i=0; i<n; i++){
        cin>>board[i];
    }

    vector<int> v;
    queue<pair<int,int>> q;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(visited[i][j]||board[i][j] == '0') continue;

            q.push({i,j});
            visited[i][j] = 1;
            int area = 0;

            while(!q.empty()){
                pair<int,int> cur = q.front();
                q.pop();
                area++;

                for(int dir=0; dir<4; dir++){
                    int nx = cur.first + dx[dir];
                    int ny = cur.second + dy[dir];

                    if(nx<0||nx>=n||ny<0||ny>=n) continue;
                    if(visited[nx][ny] || board[nx][ny] == '0') continue;

                    q.push({nx,ny});
                    visited[nx][ny] = 1;
                }
            }

            v.push_back(area);
        }
    }

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

    cout<<v.size()<<"\n";
    for(auto a : v)
        cout<<a<<"\n";

    return 0;
}

 

 

결과