[백준] 단지번호붙이기 2667번 (c++)

출처 : 2667번: 단지번호붙이기 (acmicpc.net)

2667번: 단지번호붙이기

풀이 방법

BFS를 이용한 완전 탐색 문제이다 

이중 for루프를 돌며 방문하지 않았으며 집인 곳이 보이면 BFS를 그 지점 부터 시작하여 연결된 덩어리의 개수를 

세어주면 된다.

실수

for (int i = 0;i < N;i++) {
        for (int j = 0;j < N;j++) {
            if (board[i][j] == '1') {
                if (visited[i][j] == 0) {                    
                    house_num.push_back(BFS(i, j));
                    visited[i][j] = 1;
                    board[i][j] = '0';
                }
            }
        }
    }

 

위 코드와 같이 메인 함수에서 BFS를 호출하고 나서 visited, board를 바꾸어 주어서 첫 번째 지점이 2번 count 되었다

#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;
int visited[25][25];
vector<string> board;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int N;

int BFS(int y, int x) {
    queue<pii> que;
    que.push(make_pair(y, x));
    int num = 1;

    while(!que.empty()) {
        y = que.front().first;
        x = que.front().second;
        que.pop();
        for (int i = 0;i < 4;i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) {
                if (board[nextY][nextX] == '1') {
                    if (visited[nextY][nextX] == 0) {
                        visited[nextY][nextX] = 1;
                        board[nextY][nextX] = '0';                        
                        que.push(make_pair(nextY, nextX));
                        num++;
                    }
                }
            }
        }

    }
    return num;
}
int main() {
    cin >> N;
    memset(visited, 0, sizeof(visited));
    vector<int> house_num;
    for (int i = 0;i < N;i++) {
        string st;
        cin >> st;
        board.push_back(st);
    }
    for (int i = 0;i < N;i++) {
        for (int j = 0;j < N;j++) {
            if (board[i][j] == '1') {
                if (visited[i][j] == 0) {
                    visited[i][j] = 1;
                    board[i][j] = '0';
                    house_num.push_back(BFS(i, j));
                }
            }
        }
    }
    sort(house_num.begin(), house_num.end());
    cout << house_num.size() << endl;
    for (int i = 0;i < house_num.size();i++) {
        cout << house_num[i] << endl;
    }
    return 0;
}