paizaラーニングレベルアップ問題集の「島探し」をやってみた

paiza×Qiita記事投稿キャンペーンということで、paizaラーニングレベルアップ問題集の[島探し](https://paiza.jp/works/mondai/s_rank_skillcheck_sample/search-island)をやってみました。
- - -
黒マス(`1`)の塊をまとめた島の数を計算する問題、即ち連結成分を求める問題は、[深さ優先探索](https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2)、[幅優先探索](https://ja.wikipedia.org/wiki/%E5%B9%85%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2)、[ユニオンファインド](https://algo-method.com/descriptions/132)等のアルゴリズムが用いられます。これらについてよく分からないという方は、リンクやタグを貼っておきますので、本記事での説明は省略させていただきます。

今回は、グラフ（Vertex(頂点)とEdge(辺・枝)）ではなく、グリッド（座標）に適用します。黒マス(`1`)を頂点、上下左右も黒マスならばそのマスとの間に辺があると見ます。
- - -
###### [深さ優先探索](https://paiza.jp/works/mondai/bfs_dfs_problems)
今回はC言語で、再帰関数で実装します。（再帰関数を用いない深さ優先探索の実装方法もあります。次の幅優先探索でヒントを示しておきます）
```c
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

int D[][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

void dfs(int n, int m, bool A[n][m], bool B[n][m], int y, int x) {
	B[y][x] = true;
	for (int d = 0; d < sizeof(D) / sizeof(D[0]); d++) {
		int i = y + D[d][0];
		int j = x + D[d][1];
		if (0 <= i && i < n && 0 <= j && j < m && A[i][j] && !B[i][j]) {
			dfs(n, m, A, B, i, j);
		}
	}
}

int main() {
	int m, n;
	scanf("%d %d", &m, &n);
	bool A[n][m];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%hhd", &A[i][j]); //これでbool型として受け取れる
		}
	}
	bool B[n][m]; //一般にvisitedという変数名が付けられることが多い
	memset(B, false, sizeof(B));
	int count = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (A[i][j] && !B[i][j]) {
				dfs(n, m, A, B, i, j);
				count++; //連結成分数をインクリメント
			}
		}
	}
	printf("%d\n", count);
}
```
Pythonで再帰関数を実装する場合
```py
from sys import setrecursionlimit
setrecursionlimit(1e6)
```
の“おまじない”を忘れないでください。今回は最大$10^6$マスあるので、少し多めに`setrecursionlimit(1<<20)`（$1,048,576$）くらいにしておいたほうがいいかも。
- - -
###### [幅優先探索](https://paiza.jp/works/mondai/bfs_dfs_problems)
こちらはC++で、キューで実装してみます。
```cpp
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

const vector<pair<int, int>> D = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

void bfs(int n, int m, const vector<vector<bool>> &A, vector<vector<bool>> &B,
		int y, int x) {
	queue<pair<int, int>> Q; //ここをstackにすれば深さ優先になる
	Q.push( { y, x });
	B[y][x] = true;
	while (!Q.empty()) {
		pair<int, int> p = Q.front();
		Q.pop();
		for (pair<int, int> d : D) {
			int i = p.first + d.first;
			int j = p.second + d.second;
			if (0 <= i && i < n && 0 <= j && j < m && A[i][j] && !B[i][j]) {
				Q.push( { i, j });
				B[i][j] = true;
			}
		}
	}
}

int main() {
	int m, n;
	cin >> m >> n;
	vector<vector<bool>> A(n, vector<bool>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int a;
			cin >> a;
			A[i][j] = !(!a);
		}
	}
	vector<vector<bool>> B(n, vector<bool>(m, false));
	int count = 0;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			if (A[y][x] && !B[y][x]) {
				bfs(n, m, A, B, y, x);
				count++; //連結成分数をインクリメント
			}
		}
	}
	cout << count << endl;
}
```
- - -
###### [ユニオンファインド](https://paiza.jp/works/mondai/union_find_kraskal)
ユニオンファインドで連結成分の数を計算することもできます。が、グリッドに適用したのは初めてです。
C、C++と来たので、C#で書いてみます。（注：C・C++とC#は別物です!!）
```cs
using System;
using System.Linq;

class UnionFind
{
    private readonly int[][][] parent;
    private readonly int[][] rank;

    private int[] Root(int i, int j)
    {
        if (this.parent[i][j].SequenceEqual(new int[] { i, j }))
        {
            return new int[] { i, j };
        }
        Array.Copy(Root(this.parent[i][j][0], this.parent[i][j][1]), this.parent[i][j], 2);
        return new int[] { this.parent[i][j][0], this.parent[i][j][1] };
    }
    // ↑単にreturn parent[i][j]とすると“参照”を返すので注意

    public bool Unite(int y, int x, int i, int j)
    {
        int[] r0 = Root(y, x);
        int[] r1 = Root(i, j);
        // ↑Rootで参照返しをすると、経路圧縮によりr0の座標が変わってしまう可能性あり
        if (r0.SequenceEqual(r1))
        {
            return false;
        }
        if (rank[r0[0]][r0[1]] < rank[r1[0]][r1[1]])
        {
            Array.Copy(r1, this.parent[r0[0]][r0[1]], 2);
        }
        else
        {
            if (rank[r0[0]][r0[1]] == rank[r1[0]][r1[1]])
            {
                rank[r0[0]][r0[1]]++;
            }
            Array.Copy(r0, this.parent[r1[0]][r1[1]], 2);
        }
        return true;
    }
    
    public UnionFind(int n, int m)
    {
        this.parent = new int[n][][];
        this.rank = new int[n][];
        for (int i = 0; i < n; i++)
        {
            this.parent[i] = new int[m][];
            this.rank[i] = new int[m];
            for (int j = 0; j < m; j++)
            {
                this.parent[i][j] = new int[] { i, j };
                this.rank[i][j] = 0;
            }
        }
    }
}

class Program
{
    static void Main()
    {
        string[] strings = Console.ReadLine().Split();
        int m = int.Parse(strings[0]);
        int n = int.Parse(strings[1]);
        UnionFind unionFind = new UnionFind(n, m);
        int count = 0;
        bool[][] A = new bool[n][];
        for (int i = 0; i < n; i++)
        {
            strings = Console.ReadLine().Split();
            A[i] = new bool[m];
            for (int j = 0; j < m; j++)
            {
                if (strings[j].Equals("1")) A[i][j] = true;
                else if (strings[j].Equals("0")) A[i][j] = false;
                else throw new Exception();
                // 黒マスなら全部バラバラの成分として連結成分数をインクリメント
                count += A[i][j] ? 1 : 0;
            }
        }
        for (int y = 0; y < n; y++)
        {
            for (int x = 0; x < m; x++)
            {
                if (A[y][x])
                {
                    // 右と下だけ確認。
                    // 隣の黒マスとUniteできたら連結成分数をデクリメント。
                    int j = x + 1; // 右
                    if (j < m && A[y][j])
                    {
                        if (unionFind.Unite(y, x, y, j)) count--;
                    }
                    int i = y + 1; // 下
                    if (i < n && A[i][x])
                    {
                        if (unionFind.Unite(y, x, i, x)) count--;
                    }
                }
            }
        }
        Console.WriteLine(count);
    }
}
```