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

自己紹介

大阪大学2回生で競技プログラミング部rainbou副部長、Atcoder緑
X:https://x.com/e4h99rhQ7I24670

問題文 島探し (paizaランク S 相当)　URL

解説

この問題はSランク問題のなかでは基礎的な問題だと思います。特に、初めてSランク問題に挑戦さあれる方には特におすすめです。
Atcoderで出題されればおそらくdiff400くらいだろうと思われます。

解法自体は非常にシンプルでUnionFindや幅優先探索などなんでも解けると思います。ここでは、一番簡単で分かりやすいであろう幅優先探索を使った解説をしていきます。

グリッド上を全探索し１が出てきたらansを+=1してそこに隣接している１のマスを０に変えていけばいいです。その後、変更されたマスをqueに入れてを繰り返しやっていく感じになります。
計算量はO(HW)です。

※ここでは入力例にあったN, Mを用いずにH, Wとしています。これは多くのグリッド問題がH, Wを用いるため、それにのっとって、ほかの問題に応用の聞きやすいようにしています。

実装例

from queue import Queue
W, H = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
ans = 0
DIJ = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def in_board(x, y):
    if 0 <= x < H and 0 <= y < W:
        return True
    return False

def bfs(i, j):
    que = Queue()
    que.put((i, j))
    A[i][j] = 0
    while not que.empty():
        i, j = que.get()
        for di, dj in DIJ:
            x, y = i+di, j+dj
            if not in_board(x, y):
                continue
            if A[x][y] == 0:
                continue
            A[x][y] = 0
            que.put((x, y))

for i in range(H):
    for j in range(W):
        if A[i][j] == 0:
            continue
        ans += 1
        bfs(i, j)

print(ans)