グラフ問題で最初に見るのは、答えが「到達できるか」なのか「最短手数」なのか、それとも候補経路ごとの条件判定なのかです。到達性や連結性だけを調べ、最短性を求めないならDFSを選びます。すべての辺の移動コストが同じで最小辺数や最小手数が必要ならBFSを選びます。右や下などの選択をすべて試し、現在の経路だけで成立する条件を判定するなら、経路内バックトラッキングを使います。
DFSとBFSはどちらも到達可能な頂点を調べられますが、探索の順序が違います。DFSは最後に追加した候補から取り出して一方向へ深く進み、BFSは先に追加した候補から取り出して距離の層を保ちます。そのため、BFSの最短距離の説明を、DFSで最初に見つけた経路へそのまま当てはめることはできません。辺ごとに異なる重みがある最短路も、このページの通常のBFSの対象外です。
探索中に次に調べる候補を入れておく場所を frontier と呼びます。DFSではPython公式のlistをstackとして使う説明どおり末尾へ追加して末尾から取り出し、BFSではdequeのappendとpopleftの説明どおり末尾へ追加して先頭から取り出します。三つの問題をこの違いと、探索済みの印をいつまで保持するかという観点で読みます。
| 問題文から読む条件 | 選ぶ方法 | frontierと状態 |
|---|---|---|
| 始点から届く頂点やグラフの連結性を知りたい | 反復DFS | list のstackと、探索全体で保持する visited |
| 同じコストの移動で最小辺数や最小手数を知りたい | BFS | deque のqueueと、発見時に確定する distance |
| 候補経路を列挙し、経路ごとの値や選択の条件を判定したい | 経路内バックトラッキング | 再帰呼び出しが現在経路を表し、分岐から戻るときに状態を元へ戻す |
頂点と辺を隣接リストに置き換える
まず、問題の対象をグラフとして読める形にします。対象となる場所や状態を頂点、一つの操作で移れる関係を辺と呼びます。頂点から直接移れる頂点を一覧にしたものが隣接リストです。無向グラフでは、頂点1から頂点2へ移れるなら頂点2から頂点1へも移れるため、入力した辺を二つの頂点のリストへ両方向に追加します。
頂点1から頂点5までを、辺1-2、1-3、2-4、4-5、3-5で結んだ小さなグラフを考えます。各頂点の隣接リストを頂点番号の小さい順に並べると、1は2と3、2は1と4、3は1と5、4は2と5、5は3と4へ移れます。この同じ辺集合をDFSとBFSの両方で追うと、データ構造の違いだけで探索順が変わることが分かります。
| 頂点 | 隣接リスト |
|---|---|
| 1 | 2, 3 |
| 2 | 1, 4 |
| 3 | 1, 5 |
| 4 | 2, 5 |
| 5 | 3, 4 |
マス目も同じモデルへ置き換えられます。空いているマスを頂点、上下左右へ一マス移る操作を辺とみなすと、盤面を明示的な辺の一覧なしで探索できます。ABC007 Cではこの読み替えにより、グリッド上の最短手数をBFSで求めます。
同じグラフをDFSのstackで追う
頂点1から探索を始め、未発見の隣接頂点をstackへ入れます。stackへ入れる時点を発見とし、stackから取り出して隣接リストを調べる時点を処理と区別します。頂点1で小さい番号を先に処理したいので、stackへは3、2の順に積みます。最後に積んだ2が先に取り出されるためです。
| 操作 | stack | 発見済み | 変化の理由 |
|---|---|---|---|
| 開始 | [1] | {1} | 始点1をstackへ積み、同時に発見済みにします。 |
| 1を取り出し、3、2を追加 | [3, 2] | {1, 2, 3} | 隣接リスト1の2、3を調べ、逆順に積むことで2を先に取り出します。 |
| 2を取り出し、4を追加 | [3, 4] | {1, 2, 3, 4} | 2の隣接頂点1は発見済みなので飛ばし、4だけを積みます。 |
| 4を取り出し、5を追加 | [3, 5] | {1, 2, 3, 4, 5} | 4から2は発見済みなので飛ばし、5を積みます。 |
| 5、3の順に取り出して終了 | [] | {1, 2, 3, 4, 5} | 5と3の未発見の隣接頂点は残っていません。 |
処理順は1、2、4、5、3です。頂点5へ最初に届いた経路は1-2-4-5で、辺は3本あります。同じ頂点5へは1-3-5という2本の経路もありますが、DFSは先に見つけた経路の短さを保証しません。後で掲載するA62のコードでは、表の「追加」が stack.append(next_vertex)、「取り出し」が stack.pop() に対応します。
同じグラフをBFSのqueueで追う
BFSでは始点1の距離を0として、queueから先に入った頂点を先に取り出します。1を処理すると2と3が距離1で見つかり、2を処理すると4が距離2で見つかります。その後に3を処理して5が距離2で見つかるため、頂点5へ初めて距離を設定した値が最小手数になります。
| 操作 | queue | distance | 変化の理由 |
|---|---|---|---|
| 開始 | [1] | 1:0 | 始点1をqueueへ入れ、距離0を設定します。 |
| 1を取り出し、2、3を追加 | [2, 3] | 1:0, 2:1, 3:1 | 1から一辺で届く頂点へ、1を足した距離を設定します。 |
| 2を取り出し、4を追加 | [3, 4] | 1:0, 2:1, 3:1, 4:2 | 2の隣接頂点1は発見済みで、4だけが距離2になります。 |
| 3を取り出し、5を追加 | [4, 5] | 1:0, 2:1, 3:1, 4:2, 5:2 | 3から5へ一辺で進めるため、5を距離2で発見します。 |
| 4、5を取り出して終了 | [] | 1:0, 2:1, 3:1, 4:2, 5:2 | 距離の小さい層から処理し、候補がなくなります。 |
処理順は1、2、3、4、5です。距離1の2と3を処理してから距離2の4と5を処理するため、後から短い経路で更新し直す必要がありません。後で掲載するABC007 Cのコードでは、表の追加が queue.append((next_row, next_col))、取り出しが queue.popleft()、距離の記録が distance[next_row][next_col] = distance[row][col] + 1 に対応します。
visitedを探索全体と経路ごとに使い分ける
通常の到達探索では、頂点をstackやqueueへ入れた時点で発見済みの印を付け、探索が終わるまで外しません。先に印を付けることで、同じ頂点が複数の親から重複してfrontierへ入ることを防ぎ、無向辺を行き来する閉路でも処理が止まります。A62の visited とABC007 Cの distance != -1 は、この一回の探索全体で生きる状態です。
バックトラッキングでは、探索全体で訪れた頂点を記録するのではなく、現在の候補経路だけの状態を持ちます。新しい選択を加えて子を調べ、子から戻る直前にその選択を取り除きます。そうすると、別の分岐は親の経路の状態から始められます。
| 状態 | 保持する範囲 | 戻るときの処理 |
|---|---|---|
| A62のDFS | 始点から到達した頂点全体 | 取り除かない |
| ABC007 CのBFS | 始点から距離を確定したマス全体 | 取り除かない |
| ABC293 Cのバックトラッキング | 現在の始点から終点までの候補経路上の値 | その呼び出しで追加した値だけ取り除く |
ABC293 Cで数える条件は、右または下に進む一つの経路上で、始点と終点を含む通過マスの値がすべて互いに異なることです。値の積が経路ごとに異なるかを調べる問題ではありません。したがって、同じ値を含むかを判定する集合は、頂点の到達済み表ではなく現在経路に対応させます。
A62を反復DFSで解く
A62の公式問題文は、頂点数 N、辺数 M の単純無向グラフが連結かを判定します。制約は、N と M がそれぞれ100,000以下で、N=1 や M=0 も含みます。N と M は大きくなり得るため、ここでは再帰の深さに依存しない明示的なstackを使います。反復DFSの探索骨格と O(N + M) の計算量は、ABC373 Dの公式解説に示される隣接リストとstackの扱い、および先ほどのPython公式資料と対応します。
入力の頂点番号は1から始まるため、読み込み直後に1を引いて配列の添字へ変換します。無向辺は graph[a].append(b) と graph[b].append(a) の両方へ追加します。始点0を発見済みにしてstackへ入れ、未発見の隣接頂点を見つけた時点で印を付けてからstackへ追加します。
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
a, b = map(int, input().split())
a -= 1
b -= 1
graph[a].append(b)
graph[b].append(a)
visited = [False] * N
stack = [0]
visited[0] = True
while stack:
vertex = stack.pop()
for next_vertex in graph[vertex]:
if visited[next_vertex]:
continue
visited[next_vertex] = True
stack.append(next_vertex)
if all(visited):
print("The graph is connected.")
else:
print("The graph is not connected.")始点を先に visited としてstackへ入れ、以後も、取り出した頂点の未発見の隣接頂点だけを visited にしてstackへ追加します。したがってstackへ入る頂点は、必ずすでに到達した頂点と辺で結ばれています。始点から到達可能な頂点への経路を一つ考えると、その経路上で最初にまだ発見されていない頂点の直前には、発見済みの頂点があります。その頂点が取り出されたときに未発見の隣接頂点が追加されるため、この操作を繰り返せば、始点から辺をたどれる頂点をすべて発見できます。一方、始点とつながっていない頂点は、発見済みの頂点の隣接頂点になることがなく、stackへ追加されません。追加前に visited を真にするので、複数の辺から同じ頂点へ到達しても重複してstackへ積みません。よって終了時の all(visited) が真であることは、無向グラフの全頂点が始点から到達可能であることと同値であり、連結性を正しく判定できます。ただし、DFSの発見順は距離順ではありません。stackの順序で深く進むため、最初に発見した経路が始点からの最短距離になる保証はなく、距離を求めるときはBFSの層順を使います。
隣接リストを作る時間と領域を含めた時間計算量は O(N + M) です。各頂点を一度発見し、無向辺を表す各方向の隣接項目を高々一度調べるためです。グラフを保存する領域は O(N + M)、グラフ以外の visited とstackは O(N) です。
N=1、M=0 なら、始点だけを訪問して all(visited) が真になるため連結と出力します。孤立頂点が一つでも残れば全要素が真にならず、非連結と出力します。一般グラフで再帰の深さが頂点数まで伸びる場合にも、掲載コードは明示stackを使うのでPythonの再帰上限に依存しません。
ABC007 CをBFSで解く
ABC007 Cの公式問題文は、壁で囲まれたグリッドの空きマスを上下左右へ移動し、始点から終点までの最小手数を求める問題です。R と C はそれぞれ50以下です。空きマスを頂点、上下左右の一手を同じコストの辺とみなします。問題文の距離層とFIFO queueの説明、および公式解説PDFのBFSの整理に合わせ、距離0の始点から順に確定させます。
座標は1から始まるので、四つの座標を読み込んだ後に1を引きます。distance を -1 で初期化し、始点だけを0にします。queueから取り出したマスの上下左右を調べ、盤面の外、壁、または発見済みのマスは飛ばします。未発見の空きマスへは親の距離に1を足してからqueueへ入れます。
from collections import deque
R, C = map(int, input().split())
start_row, start_col = map(int, input().split())
goal_row, goal_col = map(int, input().split())
start_row -= 1
start_col -= 1
goal_row -= 1
goal_col -= 1
maze = [input().strip() for _ in range(R)]
distance = [[-1] * C for _ in range(R)]
distance[start_row][start_col] = 0
queue = deque([(start_row, start_col)])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
row, col = queue.popleft()
for d_row, d_col in directions:
next_row = row + d_row
next_col = col + d_col
if not (0 <= next_row < R and 0 <= next_col < C):
continue
if maze[next_row][next_col] == "#":
continue
if distance[next_row][next_col] != -1:
continue
distance[next_row][next_col] = distance[row][col] + 1
queue.append((next_row, next_col))
print(distance[goal_row][goal_col])queueは先に入れたマスから取り出すため、距離 d のマスを処理している時点で、距離 d+1 のマスが先に処理されることはありません。未発見のマスへ初めて距離を設定するとき、その値は始点からの最小手数です。上下左右の通行可能な辺をすべて調べるため、到達可能な終点の距離を漏れなく求められます。
各マスを高々一度queueへ入れ、各マスで4方向だけを見るため、時間計算量は O(RC) です。distance とqueueを合わせた追加領域も O(RC) です。Python公式のdequeは両端操作がおおよそ O(1) と説明されているため、先頭削除に要素移動が生じる list.pop(0) ではなく popleft() を使います。
入力座標の変換を忘れると、始点や終点が一つずれます。公式条件では盤面の外周が壁で、始点と終点は空きマス、終点への到達も保証されていますが、コードでは配列境界も確認しています。すべての移動コストが1でない問題へ、この距離初回確定の説明をそのまま広げることはできません。ここでの到達不能値 -1 はコードの初期値であり、ABC007 Cの公式入力では終点へ到達できます。
ABC293 Cを経路内バックトラッキングで解く
ABC293 Cの公式問題文では、H 行 W 列の盤面を左上から右下へ、右または下だけに進みます。始点と終点を含む一つの経路上で、通ったマスの整数がすべて互いに異なる経路数を数えます。公式解説も各経路を固定して値の重複を判定する方針を示しています。ここで判定するのは値の積の違いではなく、同じ経路上に同じ値があるかどうかです。
H と W は2以上10以下なので、右へ進む回数と下へ進む回数を決めた全経路を列挙できます。経路数を P = C(H + W - 2, H - 1) と置くと、各経路で長さ H + W - 1 の値を確認する安全な時間上界は O(P(H + W)) です。再帰の深さは最大19で、現在経路の集合と再帰stackを合わせた追加領域は O(H + W) です。
再帰関数へ入った時点で、集合には始点から一つ前のマスまでの値が入っています。現在マスの値がすでにあれば、その経路は条件を満たさないので0を返します。新しい値なら集合へ追加して下と右の子を調べ、呼び出しから戻る直前に、その呼び出しで追加した値を取り除きます。早期returnした呼び出しは値を追加していないため、取り除く処理も行いません。
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
values_on_path = set()
def dfs(row, col):
value = A[row][col]
if value in values_on_path:
return 0
values_on_path.add(value)
if row == H - 1 and col == W - 1:
count = 1
else:
count = 0
if row + 1 < H:
count += dfs(row + 1, col)
if col + 1 < W:
count += dfs(row, col + 1)
values_on_path.remove(value)
return count
print(dfs(0, 0))このコードは、現在の関数呼び出しに対応する経路の値だけを values_on_path に保持します。始点から終点まで重複なしで到達した場合だけ1を数え、下へ進む分岐と右へ進む分岐をすべて合計します。戻るときに集合を親の状態へ戻すため、ある分岐で使った値が別の分岐の判定へ残りません。これが通常のDFSで使う全体visitedとの違いです。
2行2列で始点と終点の値が同じなら、どちらの経路もその二つの値を含むため答えは0です。4マスの値がすべて異なれば、右から下へ進む経路と下から右へ進む経路の2本を数えます。重複を見つけて早期returnした場合に remove しないこと、実際に add した呼び出しだけが対応する remove を実行することが境界での確認点です。
三つのコードで間違えやすい境界を確認する
| 確認する箇所 | 起きる問題 | 掲載コードでの対応 |
|---|---|---|
| 1始まりの入力座標や頂点番号 | 配列の一つ隣を参照する | 読み込み直後に1を引く |
| 無向辺の登録 | 片方向しかたどれず、連結性を誤る | 隣接リストへ両方向を追加する |
| 発見済みを付ける時点 | 同じ頂点やマスを重複してfrontierへ入れる | stackやqueueへ追加する直前に印を付ける |
| BFSの取り出し口 | 先頭削除の要素移動で効率が落ちる | deque.popleft() を使う |
| 経路内の状態を戻す時点 | 別分岐へ値が残り、正しい経路まで除外する | 追加に成功した呼び出しだけ、子探索後に remove する |
| 最短路の辺コスト | 重みが異なるのにBFSの初回距離を使う | 全辺が同じコストかを問題文で確認する |
特に visited という名前だけで状態の寿命を決めないことが大切です。A62では一回の探索全体、ABC007 Cでも一回の距離探索全体に残します。ABC293 Cでは現在経路の値だけを保持し、分岐から戻るたびに元へ戻します。問題文の条件が「全体で一度だけ」なのか「一つの候補の中だけ」なのかを先に読み分けます。
A62からABC293 Cへ三問をつなぐ
練習の順番は、A62、ABC007 C、ABC293 Cです。まずA62で、無向辺を両方向へ持つ隣接リストと、探索全体で外さない visited を確認します。次にABC007 Cで、同じ探索の骨格へFIFOと距離を加え、初回の距離設定が最短になる理由を説明します。最後にABC293 Cで、全体visitedを使わず、現在経路の値へ対象を絞って add と remove を対にします。
- A62：公式問題文を解き、
all(visited)が連結性を判定できる理由と、各頂点と各辺を何度見るかを説明します。 - ABC007 C：公式問題文と公式解説PDFを確認し、距離層順の初回発見が最短になる理由を説明します。
- ABC293 C：公式問題文と公式解説を確認し、現在経路だけの集合をなぜ戻すのか説明します。
三問を終えた時点で、問題文の答えが到達性ならDFS、同じコストの最短手数ならBFS、候補経路ごとの条件なら経路内バックトラッキングという判断を、frontierと状態の寿命に結び付けられます。コードを写すだけでなく、発見時に状態を更新する理由と、分岐から戻るときに状態を残すか戻すかを説明できれば、別の問題でも同じ骨格を使えます。
