섬의 개수 - 4963

//4963 - 섬의 개수
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, M;
int arr[50][50];
int sN;
int xarr[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int yarr[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
 
struct DisjointSet
{
    vector<int> parent, rank;
 
    DisjointSet(int n) : parent(n), rank(n, 1)
    {
        for(int i = 0; i<n; ++i)
            parent[i] = i;
    }
 
    int find(int u)
    {
        if(u == parent[u]) return u;
        return parent[u] = find(parent[u]);
    }
 
    void merge(int u, int v)
    {
        u = find(u); v = find(v);
        if(u == v) return;
        if(rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if(rank[u] == rank[v]) ++rank[v];
        --sN;
    }
};
 
 
void init()
{
    int x;
    sN = 1;
    for(int i = 0; i<N; ++i)
        for(int j = 0; j<M; ++j)
        {
            cin >> x;
            if(x)
                arr[i][j] = sN++;
            else
                arr[i][j] = 0;
        }
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (cin >> M >> N; N; cin >> M >> N)
    {
        init();
        DisjointSet set(sN);
        for(int i = 0; i<N; ++i)
            for(int j = 0; j<M; ++j)
                if(arr[i][j])
                    for(int k = 0; k<8; ++k)
                        if(i + xarr[k] >= 0 && i + xarr[k] < N 
                            && j + yarr[k] >= 0 && j + yarr[k] < M)
                                if(arr[i+xarr[k]][j+yarr[k]])
                                    set.merge(arr[i][j], arr[i+xarr[k]][j+yarr[k]]);
        cout << --sN << "\n";
    }
}

 

 

 

 

 

 

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

 

 

 

 

 

섬의 개수

union-find를 사용해 해결했습니다!