BOJ 2667번 단지번호붙이기

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/2667/2667/%EC%86%8C%EC%8A%A4.cpp

 

정올 KOI 1996 초등부1번 문제이다.

2중 반복을 통해 y, x 좌표를 확인하여 땅이 있을 때 마다 연결된 땅을 탐색해준다.

 

#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
#pragma warning(disable:4996)
 
vector<int> v;
queue<pair<int, int> > q;
int mx[4] = { -1,1,0,0 };
int my[4] = { 0,0,1,-1 };
int arr[25][25];
int T;
 
int main() {
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        for (int k = 0; k < T; k++) {
            scanf("%1d", &arr[i][k]);
        }
    }
 
    int cnt = 0;
    for (int i = 0; i < T; i++) {
        for (int k = 0; k < T; k++) {
            if (arr[i][k]) {
                cnt++;
                arr[i][k] = 0;
                int total = 0;
                q.push({ i,k });
                while (!q.empty()) {
                    int x = q.front().second;
                    int y = q.front().first;
                    q.pop();
 
                    total++;
                    for (int j = 0; j < 4; j++) {
                        int xx = mx[j] + x;
                        int yy = my[j] + y;
                        if (xx >= 0 && yy >= 0 && xx < T && yy < T && arr[yy][xx]) {
                            q.push({ yy,xx });
                            arr[yy][xx] = 0;
                        }
                    }
                }
                v.push_back(total);
            }
        }
    }
    sort(v.begin(), v.end());
    printf("%d\n", cnt);
    for (int i = 0; i < v.size(); i++) printf("%d\n", v[i]);
 
    return 0;
}