島探し (paizaランク S 相当)：

島探し (paizaランク S 相当)

背景

列の数がM、行の数がNの表があります。表の各マスは白か黒で塗られています。
黒で塗られたマスが上下左右で隣接している時、その黒マスの塊をまとめて「島」と呼びます。
例えば、以下のような4列×5行の表（M=4、N=5）があった場合

この表には以下の(1)～(3)のように3つの島が存在します。

島の数を計算して出力するプログラムを作成して下さい。

この問題は、2次元グリッド上の「島」（上下左右で隣接する黒いマスの塊）を数える問題です。DFS（深さ優先探索）またはBFS（幅優先探索）を用いて、各島を探索して数える方法で解決できます。ここではDFSを用いた解法を示します。

解法の考え方

1. グリッドの入力と準備:

   • 入力からグリッドのサイズ（列数 M、行数 N）と、各セルの状態（白か黒）を読み取ります。
   • 1 は黒（島の一部）、0 は白（空き地）を表します。

2. 探索の初期化:

   • 島の数をカウントするための変数 island_count を初期化します。
   • 訪れたマスを記録するために、2次元リスト visited を初期化します。

3. 深さ優先探索（DFS）による島の探索:

   • グリッド内の各セルを順に見ていき、まだ訪れていない黒マス（1）を見つけたら、DFSでその塊全体を探索します。
   • 新しい島を見つけるたびに island_count をインクリメントします。
   • DFSを用いて、見つけた黒マスからつながっている全ての黒マスを探索し、訪れたマスを visited に記録します。

4. 結果の出力:

   • 最終的に island_count を出力します。

実装コード

以下にPythonでの実装例を示します：

def count_islands(M, N, grid):
    def dfs(x, y):
        # 範囲外チェックと白マスまたは既訪問チェック
        if x < 0 or x >= N or y < 0 or y >= M or grid[x][y] == '0' or visited[x][y]:
            return
        # 現在のマスを訪問済みとする
        visited[x][y] = True
        # 上下左右に移動して再帰的にDFSを行う
        dfs(x + 1, y)
        dfs(x - 1, y)
        dfs(x, y + 1)
        dfs(x, y - 1)

    # 訪問チェック用のリスト
    visited = [[False] * M for _ in range(N)]
    island_count = 0

    # 全てのマスを確認
    for i in range(N):
        for j in range(M):
            if grid[i][j] == '1' and not visited[i][j]:
                # 新しい島を見つけた場合、DFSを開始して全ての連結する黒マスを訪問する
                dfs(i, j)
                island_count += 1

    return island_count

# 入力の読み込み
import sys
input = sys.stdin.read
data = input().splitlines()

M, N = map(int, data[0].split())
grid = [line.split() for line in data[1:]]

# 結果の出力
print(count_islands(M, N, grid))

入力例

4 5
0 1 0 1
1 1 0 0
0 0 1 0
1 0 0 1
1 1 1 0

出力例

3

このコードのポイント

• DFSを用いて、グリッド全体を探索し、島の数を効率的にカウントしています。
• 各セルについて、隣接するセルを再帰的に探索することで、島全体を訪問し、再び探索することを防いでいます。
• visited リストを使うことで、すでに訪れたセルを記録し、二重訪問を防止しています。