問題と適用場面
陸地を表す "1" と水を表す "0" のみを含む m × n のグリッドが与えられたとき、島の数を返します。2つの陸地セルは、水平または垂直の辺を共有している場合にのみ連結しているとみなされます。島とは、陸地セルの極大連結集合です。
制約は 1 <= m, n <= 300 です。呼び出し側の前提条件をランタイムエラーにしてしまわないよう、実装では空配列に対しても防御策を講じます。グリッドは変更可能であると仮定します。呼び出し側が元のグリッドを保持する必要がある場合は、代わりに同サイズの visited 行列を使用します。
これはソフトウェアエンジニアリングのコーディング面接における一般的なアルゴリズム問題です。行列を暗黙のグラフとしてモデル化し、連結成分を走査し、計算量分析と整合性のある実装を作成できるかが試されます。
面接官が評価するポイント
優れた回答では、各陸地セルを頂点、4方向の隣接関係を辺として扱います。これにより、「走査中に未訪問の陸地に到達するたび、新しい連結成分を発見したことになる」という重要なルールが導き出されます。それを1回カウントし、二度とカウントされないように島全体を走査してマークします。
実装の細部が重要です。隣接セルはポップ時ではなく、スタックにプッシュする時点でマークします。そうしないと、複数の隣接セルから同じセルが重複してプッシュされる可能性があります。また、反復型DFSを採用することで、グリッドの大部分が1つの島である場合に言語のコールスタックが深くなりすぎるのを防ぎます。正確な回答では、インプレースマークにより visited の行列を不要にできる一方で、明示的なスタックが最悪ケースで O(mn) の空間を占有する点にも言及します。
不十分な回答は、連結性の定義、入力の変更、正当性の不変条件、敵対的なテストケースに触れず、単に「DFSを使う」とだけ述べるようなものです。
最初に確認すべき質問
- 対角線方向は連結していますか？ この問題では4方向を使用します。8方向が連結とみなされる場合は方向リストを拡張し、結果が変わることを想定します。
- 入力の変更は許可されていますか？ 許可されている場合は、訪問済みの
"1"セルを"0"に書き換えます。許可されていない場合はvisitedを使用し、時間制限を維持しつつ O(mn) の追加メモリを使用します。 - グリッドは長方形であり、空ではありませんか？ 問題文で両方が保証されていますが、本番コードでは空の入力に対して 0 を返すようにします。ジャグ配列（各行の長さが異なる配列）の場合は、行ごとに境界を確認する必要があります。
- これは静的な1回のカウントですか、それとも陸地が追加されるごとのカウントですか？ 静的グリッドにはDFSまたはBFSが適しています。段階的な追加には素集合データ構造（Disjoint Set Union / Union-Find）が適しています。
- サイズとコールスタックの制限はどのくらいですか？ 300×300 のすべてが陸地のグリッドでは、90,000回の再帰呼び出しが発生する経路が生じる可能性があるため、この解法では明示的なスタックを使用します。
30秒での回答フレームワーク
「陸地セルを暗黙のグラフの頂点、4方向の隣接関係を辺としてモデル化します。グリッドを行ごとに走査します。残っている 1 は未処理の連結成分の始点となるため、島のカウントを1増やし、そこから反復型DFSを実行します。陸地の隣接セルをプッシュ時に 0 に変更することで、重複プッシュを防ぎます。各セルは最大1回しかプッシュされず、明示的なスタックを使用することで深い再帰を回避します。時間計算量は O(mn) で、スタックの空間計算量は最悪 O(mn) です。入力の変更が禁止されている場合は、同じ状態を visited 行列に保存します。」
ステップごとの詳細解説
ステップ 1: 単純な探索における無駄な処理を特定する
すべての陸地セルから毎回新規に探索を開始すると、同じ島を何度も走査してしまいます。隣接セルを見つけること自体はボトルネックではありません。足りないのは、探索をまたいで保持され、そのセルがすでにカウント済みの成分に属していることを記録する状態です。
全体走査と恒久的な訪問マークを組み合わせることで、この重複を排除できます。未訪問の陸地からのみ走査を開始します。
ステップ 2: カウントの不変条件を確立する
走査が (r, c) に達した時点で、それ以前の各DFSはちょうど1つの完全な島をマークし終えています。現在のセルがまだ "1" である場合、それらの探索のいずれもこのセルに到達しなかったことを意味するため、新しい島が始まる必要があり、カウントが1増えます。
DFSは4方向の陸地の辺のみをたどるため、水を越えて異なる島同士を統合することはありません。また、始点に連結しているすべての陸地セルに到達するため、この島が後で再びカウントされることもありません。これら2つの事実により、過小カウントも二重カウントも発生しないことが証明されます。
ステップ 3: プッシュ時にマークする
未マークのセルが、すでにスタックに入っている2つのセルに隣接していると仮定します。もしマークするのをポップ時まで遅らせると、両方の隣接セルからそのセルがプッシュされてしまいます。結果として正解が得られることは多いものの、スタックに重複した処理が含まれ、厳密な計算量の議論が成り立たなくなります。
発見した隣接セルは、プッシュする前に "0" に変更します。これにより、後からそのセルに向かう辺は訪問済みとして認識するため、各陸地セルがスタックに入る回数は最大1回であることが保証されます。
ステップ 4: 反復型DFSの実装
function numIslands(grid) {
if (grid.length === 0 || grid[0].length === 0) return 0;
const rows = grid.length;
const cols = grid[0].length;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let islands = 0;
for (let row = 0; row < rows; row += 1) {
for (let col = 0; col < cols; col += 1) {
if (grid[row][col] !== "1") continue;
islands += 1;
grid[row][col] = "0";
const stack = [[row, col]];
while (stack.length > 0) {
const [currentRow, currentCol] = stack.pop();
for (const [rowOffset, colOffset] of directions) {
const nextRow = currentRow + rowOffset;
const nextCol = currentCol + colOffset;
if (
nextRow >= 0 && nextRow < rows &&
nextCol >= 0 && nextCol < cols &&
grid[nextRow][nextCol] === "1"
) {
grid[nextRow][nextCol] = "0";
stack.push([nextRow, nextCol]);
}
}
}
}
}
return islands;
}走査では mn 個のセルを検査します。すべての陸地セルは最大1回プッシュされ、4つの隣接セルを確認するため、時間は O(mn) です。明示的なスタックは、すべてが陸地のグリッドにおいて O(mn) の座標を保持する可能性があります。この関数は入力を変更します。代わりにグリッドをコピーする場合も、O(mn) の時間と空間がかかります。
ステップ 5: 境界値と敵対的ケースの検証
最低限、次のテストを行います：空配列で 0 を返す、1つの水セルで 0 を返す、1つの陸地セルで 1 を返す、すべて水で 0 を返す、すべて陸地で 1 を返す、対角線でのみ接している2セルで 2 を返す、3つの分離された領域を持つサンプルで 3 を返す、300×300 のすべて陸地のグリッドで再帰コールスタックがオーバーフローしない。
また、入力変更の契約もテストします。呼び出し後に元のグリッドを必要とする別のアサーションがある場合は、事前にコピーするか visited を使用します。この選択は、隠された実装の詳細ではなく、インターフェース契約の一部とすべきです。
ステップ 6: 代替手法の比較
BFSと反復型DFSは、時間計算量および最悪ケースの空間計算量が同じです。距離の階層（最短経路など）が重要な場合はBFSを選択します。連結成分を網羅することだけが目的であれば、どちらでも適切です。再帰的DFSが適しているのは、入力が十分に小さいか、言語が十分なスタックの深さを保証している場合のみです。素集合データ構造（Union-Find）は、陸地が段階的に追加され、挿入ごとにカウントが求められる場合に有用ですが、静的な1回のカウントに対しては不要なインデックス管理や集合操作のオーバーヘッドが増えます。
高品質な回答例
「この問題は、暗黙の無向グラフにおける連結成分のカウント問題です。各 1 は頂点であり、水平または垂直に隣接する陸地同士が辺を共有します。グリッド全体を走査し、ある位置がまだ 1 である場合、それ以前の探索が到達していないため新しい島を発見したと判断してカウントをインクリメントします。その後、反復型DFSを実行してその島全体を 0 に書き換えます。
隣接セルはプッシュ時にマークすることで、隣り合う2つのセルから同じ位置が重複してプッシュされるのを防ぎます。300×300 のすべて陸地のグリッドでは再帰の経路が非常に深くなる可能性があるため、明示的なスタックを使用します。各セルは最大1回処理され、4方向を確認するため、時間計算量は O(mn)、最悪のスタック空間は O(mn) です。このバージョンは入力を変更しますが、インターフェースで入力を保持する必要がある場合は、マークを O(mn) の visited 行列に移します。対角線の非連結性、すべて水、すべて陸地、空入力などの境界ケースを検証します。」
この回答は、丸暗記した用語に頼ることなく、モデル、カウントの論拠、実装上のリスク、副作用、検証を結びつけています。
よくある間違い
- 対角線を連結として扱う → 問題の前提が変わり、島の数を過小カウントする可能性があります → 方向リストには上下左右のみを含めます。
- ポップ時にのみマークする → 複数の隣接セルから同じセルがプッシュされる可能性があります → 有効な隣接セルはプッシュする直前にマークします。
- インプレースだから空間計算量は O(1) だと主張する → 最悪ケースの明示的スタックの存在を無視しています → 最悪ケースの補助空間は O(mn) であると回答します。
- スタックの深さに触れずに再帰的DFSを使用する → 1つの大きな島によって言語のコールスタックが枯渇する可能性があります → 反復処理を使用するか、安全なサイズの上限を設定します。
- 呼び出し側のデータを無断で変更する → 後続のコードでグリッドがクリアされてしまいます → 副作用を文書化するか
visitedを使用します。 - すべての陸地セルから毎回探索を再開する → 同じ連結成分が何度も走査されます → 未訪問の陸地からのみ開始します。
- 通常の長方形のみをテストする → 空、すべて水、すべて陸地、対角線の反例が未検証のままになります → 最小ケース、極端なケース、敵対的なケースを網羅します。
フォローアップの質問と回答
フォローアップ 1: 入力を変更できない場合はどうしますか？
m × n のブール値行列を割り当て、プッシュ時にその位置を訪問済みとしてマークします。カウントの不変条件と O(mn) の時間は変わらず、追加ストレージは明示的に O(mn) となります。入力をコピーする場合も漸近的な空間コストは同じですが、セマンティクスが異なります。
フォローアップ 2: 対角線方向も連結している場合はどうなりますか？
方向リストを4方向から8方向に拡張します。探索の枠組み自体は変更ありません。まず [[1, 0], [0, 1]] のようなケースでルールを確認します（4方向の場合は 2 ですが、8方向の場合は 1 になります）。
フォローアップ 3: 陸地が1セルずつ追加され、その都度カウントを求められる場合はどうしますか？
静的なDFSを繰り返すと無駄な処理が発生します。代わりに素集合データ構造（Union-Find）を使用します。新しい陸地セルが追加されたら初期状態としてカウントを1増やし、既存の隣接する陸地セルと統合（union）します。異なる2つの集合の統合が成功するたびに、カウントを1減らします。重複して2回カウントされないよう、重複した挿入は無視する必要があります。
フォローアップ 4: 座標の範囲は膨大だが、陸地がまばら（スパース）な場合はどうしますか？
完全な行列を割り当てないようにします。ハッシュセットに陸地の座標のみを保存し、それらの座標を走査して4方向の隣接関係を調べます。陸地セルの数を k とすると、期待時間計算量は O(k) となり、訪問済みセットとスタックも O(k) になります。この結論は疎な座標リスト表現を前提としており、密なグリッド入力から直接得られるものではありません。