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

2667번: 단지번호붙이기

이제 어느정도 너비 우선 탐색 유형에 익숙해졌다.

이 문제에선 단지 수를 나타내는 변수 max_block와 단지별 집의 수를 저장할 house_count를 선언하고,

처음부터 스캔을 하며 1인 칸부터 탐색을 실시했고, 탐색을 시작할 땐 max_block에 1씩 더해주었다.

그리고 지나가는 칸 마다 max_block - 1의 값을 대입하고 house_count의 max_block - 1번 인덱스에 1을 더해준다.

이를 새로운 칸을 발견하지 못 할 때까지 반복하면 금방 끝난다.

마지막 출력을 할 땐, house_count를 오름차순으로 정렬해주고 출력하면 끝난다.

#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    int* apartment = new int[N * N];
    for (int i = 0; i < N * N; i++) {
        char c = getchar();
        if (c != '0' && c != '1')
            c = getchar();
        apartment[i] = c - '0';
    }

    const pair<int, int> adjacencies[4] = { make_pair(0, 1), make_pair(0, -1), make_pair(-1, 0), make_pair(1, 0) };
    queue<pair<int, int>> BFS;
    int max_block = 1;
    int house_count[315];
    for (auto& cnt : house_count)
        cnt = 0;
    bool found = true;
    while (found) {
        found = false;
        for (int i = 0; i < N * N; i++)
            if (apartment[i] == 1) {
                BFS.push(make_pair(i % N, i / N));
                found = true;
                break;
            }
        if (!found) break;

        max_block++;
        while (BFS.size()) {
            int x = BFS.front().first;
            int y = BFS.front().second;
            while (apartment[y * N + x] != 1) {
                BFS.pop();
                if (BFS.empty())
                    goto OUT;
                x = BFS.front().first;
                y = BFS.front().second;
            }

            for (auto& adjacency : adjacencies) {
                int chg_x = x + adjacency.first;
                int chg_y = y + adjacency.second;
                if (chg_x >= 0 && chg_x < N && chg_y >= 0 && chg_y < N)
                    if (apartment[chg_y * N + chg_x] == 1)
                        BFS.push(make_pair(chg_x, chg_y));
            }

            apartment[y * N + x] = max_block;
            house_count[max_block - 1]++;

            BFS.pop();
        }
    OUT:;
    }

    printf("%d\n", max_block - 1);
    sort(house_count + 1, house_count + max_block);
    for (int i = 1; i < max_block; i++)
        printf("%d\n", house_count[i]);

    delete[] apartment;
    return 0;
}

처음 제출했을 때는 틀렸습니다.를 받았는데, 출력의 첫 줄에 총 단지수를 출력하라는 메세지를 제대로 안 읽었었다.

그걸 고치고 바로 맞았습니다!를 받았다.