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

🔗알고리즘 문제

이제 정말 그래프 탐색 문제에 익숙해졌구나라고 느낀 문제. 최근 그래프 탐색에 관해 공부한 후 한동안 그래프 탐색 문제만 풀었는데, 이제 간단한 그래프 탐색 문제는 문제를 보자마자 바로바로 풀 수 있게 되어 매우 뿌듯했다 &-&

문제 분석

이 문제는 0과 1로 이루어진 2차원 배열이 주어질 때, 이 배열에서 1끼리 뭉쳐있는 덩어리가 몇개인지 판단하는 문제이다.

대각선으로 연결 되있는 경우는 무시한다.

발상 & 알고리즘 설계

해당 2차원 배열을 그래프라고 생각하면 결국 한 그래프마다 몇 개의 노드가 연결되있는지를 구하는 간단한 문제이다.

2중 for문을 진행하며 아직 탐사하지 않았고, 0이 아닌 곳을 발견하면 해당 부분이 그래프의 시작점이라고 생각하고 연결되어 있는 모든 1을 탐사하였다.

탐색이 끝난 후 결국 탐사 횟수가 연결되 있는 단지의 수가 되므로 탐사 횟수를 오름차순으로 정렬된 우선순위 큐에 담아주었다.

코드

#include<iostream>
#include<queue>
#include<string>

using namespace std;

int n;
int arr[26][26] = {};

int destX[4] = { -1, 1, 0, 0 };
int destY[4] = { 0, 0, -1, 1 };

priority_queue<int, vector<int>, greater<int>> answer;

int search(int x, int y){
    queue<pair<int, int>> q;
    int room = 0;

    arr[y][x] = 2;
    q.push({ x, y });

    while(q.empty() == false){
        pair<int, int> node = q.front();
        q.pop();

        ++room;

        for(int i = 0; i < 4; i++){
            int posX = node.first + destX[i];
            int posY = node.second + destY[i];

            if(posX < 0 || posX > n || posY < 0 || posY > n)
                continue;
            if(arr[posY][posX] == 0)
                continue;
            if(arr[posY][posX] > 1)
                continue;

            arr[posY][posX] = 2;
            q.push({ posX, posY });
        }
    }

    return room;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n;

    for(int i = 0; i < n; i++){
        string line;
        cin >> line;
        for(int j = 0; j < n; j++){
            arr[i][j] = line[j] - '0';
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(arr[i][j] == 0 || arr[i][j] > 1)
                continue;

            answer.push(search(j, i));
        }
    }

    cout << answer.size() << "\n";
    while(answer.empty() == false){
        cout << answer.top() << "\n";
        answer.pop();
    }
}