深さ優先探索 (DFS) でグリッドのいちばん大きい島の広さを求める

陸と海のマスが並んだ地図から、上下左右につながった陸のまとまり (島) のうち、いちばん広い島のマスの数を返します。島を見つけたら塗りつぶしながら数える練習です。

海外で定番の問題リスト 4 本には入っていません

問題

海の上から撮った地図を、2 次元の並び grid で受け取ります。各マスは数の 1 (陸) か 0 (海) です。上下左右のどれかで隣り合う陸どうしは、同じ島に属します。島の広さは、その島の陸のマスの数です。いちばん広い島の広さを返す関数を書いてください。陸が 1 つも無ければ 0 を返します。

斜めに隣り合うだけの陸は、つながっていないものとします
地図の外側は、すべて海だと考えます
行の数と列の数は、どちらも 1 以上 50 以下です。どの行も同じ長さです
関数の中で grid を書き換えてかまいません

入力と出力の例

例 1

左上の島は 4 マス、右下の島は 3 マス、右上の島は 1 マスです。いちばん広いのは 4 です。

grid = [[1, 1, 0, 0, 1], [0, 1, 1, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1]]

例 2

陸がありません。

grid = [[0, 0], [0, 0]]

例 3

斜めにしか隣り合っていない陸は別々の島です。どの島も 1 マスです。

grid = [[1, 0, 1], [0, 1, 0]]

面接での聞かれ方

面接では、短く次のように渡されることが多いです。

「0 と 1 のグリッドで、1 がつながった島のうち、いちばん大きい島の面積を返してください」
島の数を数える問題のあとに、続けて出されることが多い問題です。「島の数のコードから、どこを変えましたか？」と聞かれます
書き終えると「再帰で書くと、地図が大きいとき何が起きますか？」と、呼び出しの深さを聞かれることがあります

斜めのつながりを数えるかと、入力を書き換えてよいかを最初に確かめておくと、塗りつぶす書き方を選べます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「グラフ探索と幅優先探索」に、この型の要点を表とコードでまとめています。

グラフ探索は、つながりを近い順か奥からたどります。迷路、最短の手数、講座を受ける順のような問題が同じ形です。

まず考える手順

段 1

全部のマスを左上から順に見て、まだ数えていない陸を見つけたら、そこから島全体をたどって広さを数えます。たどり終えたら、それまでのいちばん広い値と比べて残します。

段 2

島をたどるには、深さ優先探索 (DFS) を使います。見つけた陸を「次に見るマス」の山 (スタック) に積み、山から 1 つ取り出しては 1 を数え、上下左右の陸を山に積む、を山が空になるまで繰り返します。

段 3

同じ陸を 2 回数えないように、山に積むときに、そのマスを海 (0) に塗りつぶします。取り出すときに塗ると、まだ山に入っているマスを別の隣からもう一度積んでしまいます。塗りつぶしたマスは、外の繰り返しで陸として見つかることもありません。

段 4

再帰で書くこともできますが、1 つの島が 2500 マスあると、呼び出しが 2500 段まで深くなり、Python では深さの上限に当たることがあります。自分でスタックを持つ書き方なら、その心配がありません。

解答

Python

def max_island_area(grid):
    h = len(grid)
    w = len(grid[0])
    return max(
        fill(grid, r, c)
        for r in range(h)
        for c in range(w))


STEPS = ((1, 0), (-1, 0),
         (0, 1), (0, -1))


def fill(grid, r, c):
    # 陸を海に塗りながら数える
    if grid[r][c] == 0:
        return 0
    grid[r][c] = 0
    todo = [(r, c)]
    area = 0
    while todo:
        r, c = todo.pop()
        area += 1
        for dy, dx in STEPS:
            y = r + dy
            x = c + dx
            if land(grid, y, x):
                grid[y][x] = 0
                todo += [(y, x)]
    return area


def land(grid, y, x):
    if not 0 <= y < len(grid):
        return False
    row = grid[y]
    if not 0 <= x < len(row):
        return False
    return row[x] == 1

JavaScript

function maxIslandArea(grid) {
  let best = 0;
  grid.forEach((row, r) => {
    row.forEach((_, c) => {
      best = Math.max(
        best, fill(grid, r, c));
    });
  });
  return best;
}

// 陸を海に塗りながら数える
function fill(grid, r, c) {
  if (grid[r][c] === 0) {
    return 0;
  }
  const h = grid.length;
  const w = grid[0].length;
  grid[r][c] = 0;
  const todo = [[r, c]];
  let area = 0;
  while (todo.length) {
    const [y, x] = todo.pop();
    area++;
    for (const [ny, nx] of [
      [y + 1, x], [y - 1, x],
      [y, x + 1], [y, x - 1],
    ]) {
      if (ny < 0 || ny >= h ||
        nx < 0 || nx >= w) {
        continue;
      }
      if (grid[ny][nx] === 1) {
        grid[ny][nx] = 0;
        todo.push([ny, nx]);
      }
    }
  }
  return area;
}

Go

var dirs = [][2]int{
	{1, 0}, {-1, 0},
	{0, 1}, {0, -1},
}

func maxIslandArea(
	grid [][]int,
) int {
	best := 0
	for r := range grid {
		for c := range grid[r] {
			a := fill(grid, r, c)
			best = max(best, a)
		}
	}
	return best
}

// 陸を海に塗りながら数える
func fill(
	grid [][]int, r, c int,
) int {
	if grid[r][c] == 0 {
		return 0
	}
	h := len(grid)
	w := len(grid[0])
	grid[r][c] = 0
	todo := [][2]int{{r, c}}
	area := 0
	for len(todo) > 0 {
		p := todo[len(todo)-1]
		todo = todo[:len(todo)-1]
		area++
		for _, d := range dirs {
			y := p[0] + d[0]
			x := p[1] + d[1]
			if y < 0 || y >= h ||
				x < 0 || x >= w {
				continue
			}
			if grid[y][x] == 1 {
				grid[y][x] = 0
				todo = append(todo,
					[2]int{y, x})
			}
		}
	}
	return area
}

fill は、海のマスでは 0 を返します。そのため外の繰り返しでは、陸かどうかを確かめずに全部のマスで呼べます。Python の max に渡す値は、マスが 1 つ以上あるので空になりません。

計算量

時間は O(m × n) です。m と n は行と列の数です。どのマスも、外の繰り返しで 1 回、塗りつぶしで多くて 1 回積まれ、上下左右の 4 つを見るだけです
使う記憶は O(m × n) です。全部が陸なら、スタックにマスがたくさん積まれます

よくある間違い

取り出すときに塗る。同じマスが別の隣から何度も積まれ、広さを多く数えます。積むときに塗ります
島の数を返す。島の数の問題と形が似ているので、数えた広さではなく島の数を返してしまうことがあります。返すのはいちばん広い島の広さです
陸が無いときに困る。いちばん広い値を 0 から始めれば、陸が無いときもそのまま 0 を返せます
範囲を確かめる前にマスを読む。 Python は負の番号で反対の端を読んでしまい、別の島とつながったと数えます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def max_island_area(grid: list[list[int]]) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(max_island_area([[1, 1, 0, 0, 1], [0, 1, 1, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1]]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します