幅優先探索 (BFS) で知らせが全員に届くまでの分を数える

座席の表で、知らせを持つ人から上下左右の人へ 1 分ずつ知らせが広がるとき、全員に届くまでの分を数えます。始めに知らせを持つ人を全員、同時に列へ入れて段ごとに広げる練習です。

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

問題

教室の座席を 2 次元の並び grid で受け取ります。各マスは次のどれかの数です。

0 は空いている席です
1 は、まだ知らせを知らない人が座っている席です
2 は、知らせを知っている人が座っている席です

1 分たつごとに、知らせを知っている人は、上下左右で隣り合う席の、知らない人へ知らせを伝えます。伝わった人は、次の 1 分から伝える側になります。空いている席を飛び越えては伝わりません。知らない人がいなくなるまでの分を返す関数を書いてください。どれだけたっても知らせが届かない人がいるなら -1 を返します。

始めから知らない人がいなければ 0 を返します
行の数と列の数は、どちらも 1 以上 10 以下です。どの行も同じ長さです
関数の中で grid を書き換えてかまいません

入力と出力の例

例 1

左下の人から、1 分で上と右、2 分でその先、と広がります。右上の人に届くのは 4 分後です。

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

例 2

右上の人は、隣が空いている席だけなので、知らせが届きません。

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

-1

例 3

知っている人が 2 人いて、両側から同時に広がります。まん中の人に 1 分、その隣の 2 人に 1 分で、2 分後に全員に届きます。

grid = [[2, 1, 1, 1, 2]]

面接での聞かれ方

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

「グリッドに新鮮なオレンジと腐ったオレンジがあり、毎分、腐ったオレンジの隣が腐ります。全部腐るまでの分を返してください。無理なら -1 です」
1 つずつ始めの点から探す書き方を出すと、「始めの点がいくつもあるとき、まとめて 1 回で探せませんか？」と聞かれます
「始めから新鮮な物が無いときは？」と、端の答えを聞かれます

始めに知らない人がいないときと、届かない人がいるときの答えを最初に確かめておくと、最後の返し方で迷いません。

ヒント

まだ開いていません

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

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

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

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

まず考える手順

段 1

1 分ずつ盤を全部見て、知っている人の隣を知る側にする、を変化が無くなるまで繰り返す書き方がまず浮かびます。1 回で O(m × n)、繰り返しは最大 m × n 回なので、O((m × n)²) かかります。

段 2

知らせは「知っている人から、何歩で届くか」の分だけかかります。これは、幅優先探索 (BFS) で段ごとに広げると求まります。始めに知っている人が何人もいるので、その全員を最初の段として一度に列へ入れます。こうすると、それぞれの人に、いちばん近い知っている人からの歩数で届きます。

段 3

段ごとに、いまの段の人の上下左右を見て、知らない人を知る側にして、次の段に入れます。1 段進むごとに 1 分を足します。知らない人の数を始めに数えておき、伝えるたびに 1 減らします。0 になったらその時点の分が答えです。次の段が空になっても知らない人が残っていれば、もう届かないので -1 です。

段 4

伝えた人は、その場で 2 に書き換えます。次の段に入れたあとで書き換えると、同じ人を別の隣からもう一度入れてしまい、知らない人の数を減らしすぎます。

解答

Python

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


def spread_minutes(grid):
    h = len(grid)
    w = len(grid[0])
    now = []
    rest = 0
    for r in range(h):
        for c in range(w):
            v = grid[r][c]
            if v == 2:
                now += [(r, c)]
            elif v == 1:
                rest += 1
    minutes = 0
    while now and rest:
        nxt = []
        for r, c in now:
            for y, x in around(
                    grid, r, c):
                grid[y][x] = 2
                rest -= 1
                nxt += [(y, x)]
        now = nxt
        minutes += 1
    if rest:
        return -1
    return minutes


def around(grid, r, c):
    # 上下左右の、知らない人の席
    h = len(grid)
    w = len(grid[0])
    out = []
    for dy, dx in STEPS:
        y = r + dy
        x = c + dx
        if y < 0 or y >= h:
            continue
        if x < 0 or x >= w:
            continue
        if grid[y][x] == 1:
            out.append((y, x))
    return out

JavaScript

function spreadMinutes(grid) {
  const h = grid.length;
  const w = grid[0].length;
  let now = [];
  let rest = 0;
  grid.forEach((row, r) => {
    row.forEach((v, c) => {
      if (v === 2) {
        now.push([r, c]);
      } else if (v === 1) {
        rest++;
      }
    });
  });
  let minutes = 0;
  while (now.length && rest) {
    const next = [];
    for (const [r, c] of now) {
      for (const [y, x] of [
        [r + 1, c], [r - 1, c],
        [r, c + 1], [r, c - 1],
      ]) {
        const v = grid[y]?.[x];
        if (v !== 1) {
          continue;
        }
        grid[y][x] = 2;
        rest--;
        next.push([y, x]);
      }
    }
    now = next;
    minutes++;
  }
  return rest ? -1 : minutes;
}

Go

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

func spreadMinutes(
	grid [][]int,
) int {
	h := len(grid)
	w := len(grid[0])
	now := [][2]int{}
	rest := 0
	for r := 0; r < h; r++ {
		for c := 0; c < w; c++ {
			switch grid[r][c] {
			case 2:
				now = append(now,
					[2]int{r, c})
			case 1:
				rest++
			}
		}
	}
	minutes := 0
	for len(now) > 0 && rest > 0 {
		next := [][2]int{}
		for _, p := range now {
			for _, d := range steps {
				y := p[0] + d[0]
				x := p[1] + d[1]
				if y < 0 || y >= h ||
					x < 0 || x >= w ||
					grid[y][x] != 1 {
					continue
				}
				grid[y][x] = 2
				rest--
				next = append(next,
					[2]int{y, x})
			}
		}
		now = next
		minutes++
	}
	if rest > 0 {
		return -1
	}
	return minutes
}

JavaScript の grid[y]?.[x] は、行が盤の外なら undefined になり、列が外でも undefined です。どちらも 1 ではないので、範囲の確かめを 1 つの比べで済ませています。

計算量

時間は O(m × n) です。m と n は行と列の数です。どの席も段に入るのは 1 回だけで、上下左右の 4 つを見るだけです
使う記憶は O(m × n) です。1 つの段に入る席の数です

よくある間違い

知っている人を 1 人ずつ始めにして探す。人ごとに盤全体を探すと遅く、別々の人からの分をあとで合わせる手間も出ます。全員を同時に最初の段に入れます
最後の段のあとにも 1 分足す。次の段が空になったあとで分を足すと、1 分多くなります。例 1 では 5 を返してしまいます。知らない人が 0 になったら止めます
始めから知らない人がいないのに 1 分足す。繰り返しの条件に「知らない人がいる」を入れておけば、0 をそのまま返せます
伝えた人を書き換えずに段に入れる。同じ人が何度も段に入り、知らない人の数が負になります

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

main.py

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

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

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

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


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

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