[백준] 2667 - 단지번호붙이기, C++

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 본 문제는 KOI 1996 한국정보올림피아드 초등부 1번 문제다. 입력받은 배열에서 단지를 구분하고 단지 내 집의 수를 오름차순으로 출력하는 문제다. BFS를 이용하여 전체 배열 탐색을 하면 쉽게 풀 수 있다. 여기서 주의해야 점은 1개의 숫자를 입력받도록 해야한다.

1. 1개의 숫자씩 입력받기
2. 단지 탐색하기

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int d[25][25];
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
bool chk[25][25];
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &d[i][j]);
        }
    }
    vector<int> ans;
    queue<pair<int, int>> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 새로운 단지를 찾았을 때,
            if (!chk[i][j] && d[i][j] == 1) {
                int cnt = 1;
                q.push(make_pair(i, j));
                chk[i][j] = true;
                while (!q.empty()) {
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();
                    for (int i = 0; i < 4; i++) {
                        int nx = dx[i] + x;
                        int ny = dy[i] + y;
                        if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                            if (!chk[nx][ny] && d[nx][ny] == 1) {
                                q.push(make_pair(nx, ny));
                                chk[nx][ny] = true;
                                cnt += 1;
                            }
                        }
                    }
                }
                ans.push_back(cnt);
            }
        }
    }
    // 각 단지내 집의 수를 오름차순으로 정렬
    sort(ans.begin(), ans.end());
    // 단지의 개수 출력
    printf("%d\n", ans.size());
    for (int i = 0; i < ans.size(); i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}