백준2667-단지번호붙이기

문제 링크

백준 2667번 문제 바로가기

난이도

🥈실버 1

유의점

💜나처럼 cnt사용시 초기화 주의
💜입 출력 양식 제대로 확인하기

정답 코드

#include<iostream>
#include<queue>
#include<vector>
#define MAX 26
using namespace std;
vector<int> result;
bool visit[MAX][MAX] = { false, };
char map[MAX][MAX];
int n;
queue<pair<int, int>> q;
int dx[] = { 0, 1, -1, 0 };
int dy[] = { 1, 0, 0, -1 };

int bfs(int x, int y) {
    visit[x][y] = true;
    int cnt = 1;  // 각 함수 호출마다 cnt 초기화
    q.push(make_pair(x, y));
    while (!q.empty()) {
        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 (0 <= nx && nx < n && 0 <= ny && ny < n && !visit[nx][ny] && map[nx][ny] == '1') {
                visit[nx][ny] = true;
                q.push(make_pair(nx, ny));
                cnt++;
            }
        }
    }
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == '1' && !visit[i][j]) {
                result.push_back(bfs(i, j));
            }
        }
    }

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

    cout << result.size() << "\n";
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }

    return 0;
}