C++ Disjoint Set(서로소 집합)으로 섬의 개수 찾기

이 문제에서는 2차원 이진 행렬(binary matrix)이 주어지며, 우리의 목표는 Disjoint Set(서로소 집합) 자료구조를 이용해 섬의 개수를 찾는 것입니다.

섬(Island)이란 행렬 안에서 서로 연결되어 있는 하나 이상의 1들로 이루어진 영역을 의미합니다.

예시를 통해 문제를 자세히 살펴보겠습니다.

입력

bin[][] = {{ 1 0 0 0}
    {0 1 0 1}
    {0 0 0 0}
    {0 0 1 0}}

출력

설명

섬의 위치 :
    bin₀₀ - bin₁₁
    bin₁₃
    bin₃₂

해결 방법

이 문제는 서로소 집합(Disjoint Set) 자료구조를 활용해 효율적으로 해결할 수 있습니다. 먼저 행렬의 각 칸을 하나의 노드로 취급하고, 전체 행렬을 순회하면서 현재 칸의 8방향 이웃(상하좌우 및 대각선)을 검사합니다. 이웃한 칸의 값이 1이라면 union 연산을 통해 현재 인덱스와 그 이웃 인덱스를 같은 집합으로 합칩니다.

모든 순회가 끝난 후에는 두 번째 순회를 진행하면서, 값이 1인 칸에 대해 find 연산으로 해당 집합의 루트(대표 원소)를 찾습니다. 이때 해당 루트가 아직 한 번도 등장하지 않았다면(빈도가 0이라면) 섬의 개수를 1 증가시킵니다. 이렇게 하면 서로 연결된 1들은 하나의 집합으로 묶이고, 고유한 루트의 개수가 곧 섬의 개수가 됩니다.

참고로 2차원 좌표 (j, k)는 j * m + k 공식을 사용해 1차원 인덱스로 변환하여 집합에서 관리합니다.

예제 코드

아래 프로그램은 위에서 설명한 솔루션의 실제 동작을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;
class DisjointUnionSets{
    vector<int> rank, parent;
    int n;
    public:
    DisjointUnionSets(int n){
        rank.resize(n);
        parent.resize(n);
        this->n = n;
        makeSet();
    }
    void makeSet(){
        for (int i = 0; i < n; i++)
        parent[i] = i;
    }
    int find(int x){
        if (parent[x] != x){
            return find(parent[x]);
        }
        return x;
    }
    void Union(int x, int y){
        int xRoot = find(x);
        int yRoot = find(y);
        if (xRoot == yRoot)
            return;
        if (rank[xRoot] < rank[yRoot])
            parent[xRoot] = yRoot;
        else if (rank[yRoot] < rank[xRoot])
            parent[yRoot] = xRoot;
        else {
            parent[yRoot] = xRoot;
            rank[xRoot] = rank[xRoot] + 1;
        }
    }
};
int findIslandCount(vector<vector<int>> mat){
    int n = mat.size();
    int m = mat[0].size();
    DisjointUnionSets *dus = new DisjointUnionSets(n * m);
    for (int j = 0; j < n; j++){
        for (int k = 0; k < m; k++){
            if (mat[j][k] == 0)
               continue;
            if (j + 1 < n && mat[j + 1][k] == 1)
               dus->Union(j * (m) + k, (j + 1) * (m) + k);
            if (j - 1 >= 0 && mat[j - 1][k] == 1)
               dus->Union(j * (m) + k, (j - 1) * (m) + k);
            if (k + 1 < m && mat[j][k + 1] == 1)
               dus->Union(j * (m) + k, (j) * (m) + k + 1);
            if (k - 1 >= 0 && mat[j][k - 1] == 1)
               dus->Union(j * (m) + k, (j) * (m) + k - 1);
            if (j + 1 < n && k + 1 < m && mat[j + 1][k + 1] == 1)
               dus->Union(j * (m) + k, (j + 1) * (m) + k + 1);
            if (j + 1 < n && k - 1 >= 0 && mat[j + 1][k - 1] == 1)
               dus->Union(j * m + k, (j + 1) * (m) + k - 1);
            if (j - 1 >= 0 && k + 1 < m && mat[j - 1][k + 1] == 1)
               dus->Union(j * m + k, (j - 1) * m + k + 1);
            if (j - 1 >= 0 && k - 1 >= 0 && mat[j - 1][k - 1] == 1)
               dus->Union(j * m + k, (j - 1) * m + k - 1);
        }
    }
    int *c = new int[n * m];
    int islands = 0;
    for (int j = 0; j < n; j++){
        for (int k = 0; k < m; k++){
            if (mat[j][k] == 1){
                int x = dus->find(j * m + k);
                if (c[x] == 0){
                    islands++;
                    c[x]++;
                }
                else
                c[x]++;
            }
        }
    }
    return islands;
}
int main(void){
    vector<vector<int>> mat = {
        {1, 1, 0, 1, 0},
        {0, 1, 0, 1, 1},
        {1, 0, 0, 1, 1},
        {0, 0, 0, 0, 0},
        {1, 1, 1, 0, 1}
    };
    cout<<"이진 행렬의 섬의 개수는 : "<<findIslandCount(mat);
}

출력 결과

이진 행렬의 섬의 개수는 : 4

복잡도 분석

시간 복잡도: O(N × M × α(N × M)) — α는 아커만 함수의 역함수로 사실상 상수로 간주되므로, 실질적으로 O(N × M)에 가깝습니다. 여기서 N과 M은 각각 행렬의 행과 열의 크기입니다.
공간 복잡도: O(N × M) — 각 칸마다 부모(parent)와 랭크(rank) 정보를 저장하기 위한 배열이 필요합니다.