0Pricing
Competitive Programming Academy · レッスン

連結成分と Flood Fill

島を数え、領域にラベルを付けます

「連結成分と Flood Fill」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

連結成分とは何か

連結成分とは、互いに行き来できるノードのグループです。1つのグラフに複数の分離したグループが含まれることもあります。🧩

連結成分を数える

連結成分を数えるには、未訪問の各ノードから探索を開始します。新たに開始するたびに、1つの新しいグループ全体を見つけたことになります。

すべてのノードをループする

ノード1からnまでを順に確認します。まだ未訪問のノードを見つけたら、新しい連結成分を発見したことになるので探索します。

for s in range(1, n + 1):
    if not visited[s]:
        bfs_or_dfs(s)
        count += 1

グループごとに1回探索する

内側のBFSまたはDFSが連結成分全体を訪問済みにするため、外側のループが次に同じ成分を処理することはありません。

グリッドもグラフ

2次元グリッドは隠れたグラフです。各セルがノードで、隣接するセルとつながっています。これにより、定番のフラッドフィルという考え方を使えます。🗺️

4つの方向

セルからは通常、上、下、左、右に移動します。これらの移動を方向ベクトルとして保存すると、コードをすっきり保てます。

dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

グリッドの範囲内にとどまる

移動する前に、新しい行と列が範囲内にあることを確認します。この確認を省くと、インデックスエラーや誤答につながります。

if 0 <= nr < rows and 0 <= nc < cols:
    pass

1つの領域をフラッドフィルする

フラッドフィルは1つのセルから始まり、ペイントバケツツールのように、つながっている同じ種類のセルすべてに広がります。

島を数える

島を数えるには、グリッドを走査し、新しい陸地セルを見つけるたびに島全体をフラッドフィルして、個数に1を加えます。

if grid[r][c] == '1' and not seen[r][c]:
    flood(r, c)
    islands += 1

領域にラベルを付ける

フラッドフィル中に、各セルにラベルを保存できます。後から、どのセルがどの領域に属するかをすぐに判定できます。

グリッドサイズに対して線形

各セルを1回ずつ訪問するため、グリッドに対するフラッドフィルの計算量はO(rows times cols)です。競技プログラミングの制限時間にも十分収まります。

確認問題

連結成分はどのように数えますか？

まとめ

未訪問の各ノードから探索して連結成分を数え、グリッドではフラッドフィルを使って領域にラベルを付けたり、島を数えたりします。🎉

よくある質問

「連結成分と Flood Fill」レッスンは無料ですか？

はい。「連結成分と Flood Fill」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「連結成分と Flood Fill」で何を学びますか？

島を数え、領域にラベルを付けます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。

「連結成分と Flood Fill」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 入力から隣接リストを作る
  2. 重みなし最短経路のための BFS
  3. DFS、再帰、反復スタック
  4. 連結成分と Flood Fill
← Competitive Programming Academyに戻る