[BOJ 2667] 단지번호붙이기 - C++

✅[문제/Problem]
https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

✅[풀이/Explanation]

BFS 문제이다. 단순히 for 문을 돌려 1일때 큐에 좌표값을 넣고, BFS를 돌려 넓이 값을 벡터에 넣어주면 된다. 주의할 점은 입력을 받을때 숫자가 띄어져 있지 않으므로, 문자열에 입력받아야 한다. 이것이 은근 헷갈린다. 마지막으로인자를 넣은 벡터의 사이즈와 배열 값을 출력한다.

The solving method is to use BFS. iterate FOR structure, when a number in string arrays is one then By BFS we put areas into a vector container. points of notice are that when input numbers, numbers are stuck together, so we should input them into a string array. It is to be confused. in sum, we can solve a problem easily by outputting a vector's size and numbers in a vector.

✅[code]

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

string arr[40];

bool vis[40][40];

int dx[4] = {1,0,-1,0};

int dy[4] = {0,1,0,-1};

int main() {

    ios::sync_with_stdio(0);

    cin.tie(0);

    

    int N;

    cin >> N;

    for(int i=0; i<N; i++){

        cin >> arr[i];

    }

    

    vector <int> v;

    int tmp = 0;

    for(int i=0; i<N; i++){

        for(int j=0; j<N; j++){

            queue<pair<int,int>> q;

            if(arr[i][j] == '1' && vis[i][j] == 0){

                q.push({i,j});

                vis[i][j] = 1;

                tmp++;

            }

            while(!q.empty()){

                auto t = q.front(); q.pop();

                for(int i=0; i<4; i++){

                    int x = t.X + dx[i];

                    int y = t.Y + dy[i];

                    if(x<0 || x>=N || y<0 || y>= N) continue;

                    if(arr[x][y] != '1' || vis[x][y] == 1) continue;

                    vis[x][y] = 1;

                    tmp++;

                    q.push({x,y});

                }

            }

            if(tmp > 0) v.push_back(tmp);

            tmp = 0;

        }

    }

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

    cout << v.size() << '\n';

    for(int i=0; i<v.size(); i++){

      cout << v[i] << '\n';

    }

}