[BFS] BJ2667 단지 번호 붙이기

문제 출처: https://www.acmicpc.net/problem/2667

 

Solution

• Map을 순회하며 집이 있으면서(1) visit하지 않은 곳을 시작점으로 BFS를 해서 연결된 집 수를 구하고 전체 BFS 횟수를 구로 단지 수를 구한다.

Point

• 비연결 그래프에서의 BFS 탐색처럼 방문하지 않은 모든 노드를 시작점으로 여러번 BFS 하는 것이 핵심이다.

---

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int N;
bool map[27][27] = { false };
bool visited[27][27] = { false };
 
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        char line[25];
        cin >> line;
        for (int j = 1; j <= N; j++) {
            if (line[j - 1] - '0')
                map[i][j] = true;
        }
    }
}
 
void printInput() {
    cout << "N:" << N << endl;
    for (int i = 0; i <= N + 1; i++) {
        for (int j = 0; j <= N + 1; j++) {
            cout << map[i][j];
        }
        cout << endl;
    }
}
 
int houseGroupingBFS(int start_x, int start_y){
    int nHouse = 0;
    queue <pair <int, int> > q;
    q.push(make_pair(start_x, start_y));
    visited[start_x][start_y] = true;
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        nHouse++;
        for (int i = 0; i < 4; i++) {
            int next_x = cur.first + dx[i];
            int next_y = cur.second + dy[i];
            if (map[next_x][next_y] && !visited[next_x][next_y]) {
                q.push(make_pair(next_x, next_y));
                visited[next_x][next_y] = true;
            }
        }
    }
    return nHouse;
}
 
void houseGrouping() {
    int nGroup = 0;
    vector<int> vHouseList;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (map[i][j] && !visited[i][j]) {
                int nHouse = houseGroupingBFS(i, j);
                nGroup++;
                vHouseList.push_back(nHouse);
            }
        }
    }
    sort(vHouseList.begin(), vHouseList.end());
    cout << nGroup << endl;
    for (int i = 0; i < vHouseList.size(); i++) {
        cout << vHouseList[i] << endl;
    }
}
 
int main() {
    input();
    //printInput();
    houseGrouping();
    system("pause");
}