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

2667번: 단지번호붙이기

이전에 풀었던 다리만들기와 비슷한 문제이다. BFS와 DFS를 이용해 풀 수 있는데 이전의 정보를 저장할 필요가 없기에 BFS를 사용했다. 먼저 맵의 벽들을 -1로 바꿔주고 반복문을 돌면서 처음 만나는 -1에서 BFS를 돌렸다. BFS를 돌면서 -1이 해당 단지의 번호로 바꿔주게되고 -1이 아니면 돌지 않기 때문에 visit배열이 따로 필요가 없다. BFS를 돌면서 count를 세어 v에 저장해주고 오름차순으로 정렬후 단지 수와 함께 출력한다.
문제 중 오름차순으로 출력한다는 조건을 보지 못해 몇차례 다시 답을 제출했다. 문제를 잘 보자.

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

using namespace std;

int N;
int A[25][25];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
vector<int> v;

void bfs(int a, int b, int n) {
    queue<pair<int, int>> q;
    int count = 0;

    A[a][b] = n;
    q.push({ a,b });

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;

        count++;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
            if (A[ny][nx] == 0 || A[ny][nx] == n) continue;

            A[ny][nx] = n;
            q.push({ ny,nx });
        }
    }

    v.push_back(count);
}

void solution() {
    int n = 1;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (A[i][j] == -1) {
                bfs(i, j, n);
                n++;
            }
        }
    }

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

    cout << n - 1 << endl;
    for (auto elem : v) {
        cout << elem << endl;
    }
}

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

    cin >> N;

    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < N; j++) {
            A[i][j] = s[j] - '0';

            if (A[i][j] == 1) {
                A[i][j] = -1;
            }
        }
    }

    solution();

    return 0;
}