島探し問題のアルゴリズムを設計し、Pythonプログラムを作成します。基本的には、幅優先探索（BFS）を使用して、島を数えます。
アルゴリズム設計
問題の概要:
- 列の数が
M、行の数がNの表があり、黒マス (1) の塊を「島」と呼ぶ。 - 島の数を計算して出力する。
入力:
- 1行目に列の数
Mと行の数Nがスペース区切りで与えられる。 - 次の
N行に、スペース区切りでM個の数字（0または1）が与えられる。
出力:
- 島の数を一行で出力する。
擬似コード
擬似コードのステップ:
-
入力の読み取り
-
MとNを読み取る。 - 表（2次元リスト）を読み取る。
-
-
探索の準備
- 幅優先探索（BFS）用の移動方向リスト
moveを準備する。 - 島の数をカウントする変数
ansを初期化する。
- 幅優先探索（BFS）用の移動方向リスト
-
BFSで島を探索
- 各マスを調査し、黒マス (
1) なら新しい島を発見したと見なし、BFSを開始する。 - BFSでは、発見した黒マスをキューに追加し、そのマスを白マス (
0) に書き換えることで訪問済みとする。
- 各マスを調査し、黒マス (
-
結果の出力
- 島の数
ansを出力する。
- 島の数
完成したコード
以下に完成したPythonコードを示します。
# utf-8
def find_islands(m, n, atlas):
move = [[-1, 0], [0, 1], [1, 0], [0, -1]] # 移動方向（上下左右）
ans = 0 # 島の数をカウントする変数
for i in range(n):
for j in range(m):
if atlas[i][j] == "0": # 白マスはスキップ
continue
# 新しい島を発見
ans += 1
q = [(i, j)] # BFSのためのキュー
while q:
y, x = q.pop(0)
atlas[y][x] = "0" # 訪問済みのマスを白マスに書き換える
for vec in move:
next_y = y + vec[0]
next_x = x + vec[1]
# 境界チェック
if not (0 <= next_y < n and 0 <= next_x < m):
continue
if atlas[next_y][next_x] == "0": # 白マスはスキップ
continue
q.append((next_y, next_x)) # 次のマスをキューに追加
return ans
# 入力の読み取り
m, n = map(int, input().split())
atlas = [input().split() for _ in range(n)]
# 島の数を計算
result = find_islands(m, n, atlas)
# 結果の出力
print(result)
説明
-
入力の読み取り: 最初の行で
MとNを読み取り、次のN行で表を読み取ります。 - BFS探索: 各黒マスからBFSを開始し、隣接する黒マスを探索します。探索済みのマスは白マスに書き換えることで、再度探索しないようにします。
- 結果の出力: 発見した島の数を出力します。
このコードは、幅優先探索を使用して効率的に島を数えることができ、大規模な入力（最大1000×1000の表）にも対応します。
補足：幅優先探索（BFS）とは？
幅優先探索（Breadth-First Search, BFS）は、グラフやツリーの探索アルゴリズムの一つで、与えられた開始点から始めて、近隣のノードを順に探索していく方法です。BFSは、最短経路問題や連結成分の検出などに利用されます。
BFSの基本的な手順
-
初期化:
- キュー（Queue）を用意し、開始点をキューに追加します。
- 各ノードが訪問済みかどうかを記録するためのリストやセットを用意します。
-
探索:
- キューが空になるまで以下の操作を繰り返します。
- キューの先頭からノードを取り出します。
- そのノードに隣接するすべてのノードを調べ、まだ訪問していない隣接ノードをキューに追加し、訪問済みとしてマークします。
- キューが空になるまで以下の操作を繰り返します。
BFSの特徴
- 層ごとの探索: BFSは、開始点からの距離が等しいノードをすべて探索してから次の層に進むため、最短経路を見つけるのに適しています。
- キューを使用: キューを使うことで、FIFO（First In First Out）により順序を保ちながらノードを探索します。
擬似コード
以下にBFSの擬似コードを示します。
function BFS(start_node):
queue = empty queue
visited = set
# 初期化
queue.enqueue(start_node)
visited.add(start_node)
# 探索
while queue is not empty:
node = queue.dequeue()
for each neighbor of node:
if neighbor is not in visited:
queue.enqueue(neighbor)
visited.add(neighbor)
BFSの具体例
例えば、以下のようなグラフを考えます。
A
/ \
B C
/ \ \
D E F
-
初期化: キューに開始点
Aを追加します。- キュー: [A]
- 訪問済み: {A}
-
探索:
-
Aを取り出し、その隣接ノードBとCをキューに追加。- キュー: [B, C]
- 訪問済み: {A, B, C}
-
Bを取り出し、その隣接ノードDとEをキューに追加。- キュー: [C, D, E]
- 訪問済み: {A, B, C, D, E}
-
Cを取り出し、その隣接ノードFをキューに追加。- キュー: [D, E, F]
- 訪問済み: {A, B, C, D, E, F}
-
D,E,Fを順に取り出し、隣接ノードを調べますが、すべて訪問済みのためキューに追加するものはありません。
-
BFSの実際のコード例
先ほどの島探しのコードを例に、BFSがどのように使われているか説明します。
m, n = map(int, input().split())
atlas = [input().split() for _ in range(n)]
move = [[-1, 0], [0, 1], [1, 0], [0, -1]] # 上下左右の移動方向
ans = 0 # 島の数
for i in range(n):
for j in range(m):
if atlas[i][j] == "0": # 白マスはスキップ
continue
# 新しい島を発見
ans += 1
q = [(i, j)] # キューの初期化
while q:
y, x = q.pop(0) # キューからノードを取り出す
atlas[y][x] = "0" # 訪問済みとしてマーク
for vec in move:
next_y = y + vec[0]
next_x = x + vec[1]
# 境界チェック
if not (0 <= next_y < n and 0 <= next_x < m):
continue
if atlas[next_y][next_x] == "0": # 白マスはスキップ
continue
q.append((next_y, next_x)) # 隣接ノードをキューに追加
print(ans)
この例では、島を構成する黒マスをBFSで探索し、隣接するすべての黒マスを訪問済みとしてマークしています。これにより、同じ島を複数回カウントしないようにしています。
BFSは、グラフやツリーの探索において非常に有効なアルゴリズムです。特に、最短経路問題や連結成分の検出などにおいて、その特性を活かすことができます。