AtCoder ATC 001 A - 深さ優先探索 振り返り

問題概要

• 問題URL: https://atcoder.jp/contests/atc001/tasks/dfs_a
• 難易度: 基本的なDFS問題
• 制約: H×W (H,W ≤ 500) の迷路

迷路上でスタート地点’s’からゴール地点’g’まで到達可能かを判定する問題。壁’#‘は通れず、通路’.‘のみを通って移動できる。

解法アプローチ

採用した方針：深さ優先探索（DFS）

1. スタート地点から探索を開始
2. 4方向（上下左右）に対して再帰的に探索
3. 訪問済みフラグ（seen配列）で無限ループを防止
4. ゴール地点が訪問済みになれば到達可能

実装のポイント

1. 方向配列の活用

int dx[4] = {1,0,-1, 0};
int dy[4] = {0,1, 0,-1};

4方向への移動を配列で表現することで、コードがシンプルになった。

2. 境界チェック

if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;

迷路の外に出ないよう範囲チェックを実施。

3. 訪問済み管理

vector<vector<bool>> seen(H+1, vector<bool>(W+1, false));

二次元配列で各マスの訪問状態を管理。

学んだこと

良かった点

• DFSの基本的な実装パターンを確実に実装できた
• 方向配列を使った実装で可読性が高い
• 境界チェック、壁チェック、訪問済みチェックの3つの条件を適切に処理

改善点・注意点

1. seen配列のサイズ: H+1, W+1で初期化しているが、実際はH, Wで十分
2. 変数名: sx, sy（スタート座標）とtx, ty（ゴール座標）の命名は良いが、DFS内でのnh, nwはny, nxの方が一般的かも
3. 文字の探索: ‘s’と’g’の位置を別々に探しているが、1回のループでまとめて探索可能

別解・発展

• BFS（幅優先探索）: 最短経路も求めたい場合はBFSが適している
• Union-Find: 連結性の判定だけならUnion-Findでも解ける

類題への応用

このDFSの実装パターンは以下のような問題にも応用可能：

• 島の数を数える問題
• 連結成分の大きさを求める問題
• 迷路の最短経路問題（BFSに変更）

コードの時間計算量・空間計算量

• 時間計算量: O(H×W) - 各マスを最大1回ずつ訪問
• 空間計算量: O(H×W) - seen配列とDFSの再帰スタック

まとめ

典型的なグリッド上のDFS問題を確実に解くことができた。この実装パターンは競技プログラミングで頻出なので、テンプレートとして覚えておくと良い。特に方向配列を使った4方向探索のパターンは多くの問題で活用できる。