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

백준의 단지번호붙이기(2667) 문제입니다.

( www.acmicpc.net/problem/2667 )

[ 문제설명 ]

- 정사각형의 한 변의 길이를 입력받고, 맵을 입력받습니다.

- 맵은 1과 0으로 이루어져 있으며, 0은 집이 없는 곳을 1은 집이 있는 곳을 의미합니다.

- 서로 연결되어 있는(상하좌우 중 한 방향으로라도 붙어 있으면) 집들을 단지 라고 부릅니다.

- 총 몇개의 단지가 있는지 구하고, 그 단지에 있는 집의 수를 오름차순으로 출력시키면 됩니다.

[ 풀이과정 ]

1) 맵을 입력받는 과정에서, 집이 있는 곳(1) 을 입력 받을 때, 벡터에 넣어줍니다.

2) 벡터에 넣은 위치에서부터 BFS를 돌려주면 됩니다.

3) BFS를 돌리면서, BFS를 돈 횟수를 Count해줄 변수를 설정해주고, 

   BFS안에서 몇 번 실행되는지(이웃한 집의 갯수 Count)를 Count해줄 변수를 설정해서 Count 해주고,

   그 값을 벡터에 넣어줍니다.

4) BFS를 돈 횟수를 Count해준 변수를 출력시키고(단지의 갯수) 벡터에 넣어준 집의 갯수들을

   오름차순으로 정렬 후 출력시켜 주면 됩니다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
#include<vector>
 
#define endl "\n"
#define MAX 25
using namespace std;
 
int N, Area_Num;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
vector<pair<int, int>> V;
vector<int> Area_Cnt;
 
void Input()
{
    Area_Num = 0;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        string Inp;
        cin >> Inp;
        for (int j = 0; j < Inp.length(); j++)
        {
            int Temp = Inp[j] - '0';
            MAP[i][j] = Temp;
            if (MAP[i][j] == 1) V.push_back(make_pair(i, j));
        }
    }
}
 
void BFS(int a, int b)
{
    queue<pair<int,int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = true;
 
    int Cnt = 1;
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int 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 && ny >= 0 && nx < N && ny < N)
            {
                if (Visit[nx][ny] == false && MAP[nx][ny] == 1)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(nx, ny));
                    Cnt++;
                }
            }
        }
    }
    Area_Num++;
    Area_Cnt.push_back(Cnt);
}
 
void Solution()
{
    for (int i = 0; i < V.size(); i++)
    {
        int x = V[i].first;
        int y = V[i].second;
 
        if (Visit[x][y] == 0) BFS(x, y);
    }
    sort(Area_Cnt.begin(), Area_Cnt.end());
    
    cout << Area_Num << endl;
    for (int i = 0; i < Area_Num; i++)
    {
        cout << Area_Cnt[i] << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}