백준 2667 "단지 번호 붙이기" [BFS 알고리즘]

문제

 

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

접근 순서

 

1.  해당 문제는 서로 연결되었는지를 BFS 알고리즘으로 생각하여 풀이를 시작함. 

 

2. 입력에서 띄어쓰기가 없는 하나의 숫자로 들어오므로 string으로 받고 해당 문자를 char 형태로 접근하여 

    해당 문자를 2차원 배열로 접근

 

3. 다녀간 곳은 visited vector를 사용하여 기록하여 갔던 곳과 안갔던 곳을 구별함.

 

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

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

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

    int n;
    cin >> n;

    vector<string> grid(n);
    for (int i = 0; i < n; i++) 
        cin >> grid[i];

    vector<vector<int>> visited(n, vector<int>(n, 0));
    vector<int> ans;

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

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1' && visited[i][j] == 0) {

                deque<pair<int, int>> q;
                q.push_back(make_pair(i, j));
                visited[i][j] = 1;

                int cnt = 0;

                while (!q.empty()) {
                    int r = q.front().first;
                    int c = q.front().second;
                    q.pop_front();

                    cnt++;

                    for (int k = 0; k < 4; k++) {
                        int nr = r + dr[k];
                        int nc = c + dc[k];

                        if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
                        if (grid[nr][nc] == '0') continue;
                        if (visited[nr][nc] == 1) continue;

                        visited[nr][nc] = 1;
                        q.push_back(make_pair(nr, nc));
                    }
                }

                ans.push_back(cnt);
            }
        }
    }

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

    cout << ans.size() << "\n";
    for (int x : ans) cout << x << "\n";

    return 0;
}