応用情報技術者 2022年 秋期 午後 問03

解答の論理構成

1. 迷路の内側は 5×5＝25 マスです。
   ただし図1には障害物として「(4,1)、(2,2)、(3,3)、(2,4)、(3,5)、(4,5)」の6マスが示されています。
   よって “通過可能” なマスは
   25 − 6 ＝ 19 マス です。
2. 深さ優先探索は【問題文】の順番
   　「① y座標を1増やす → ② x座標を1増やす → ③ y座標を1減らす → ④ x座標を1減らす」
   　で枝を伸ばし、行き止まりになれば一つ前へ“戻る”のを繰り返します。
3. 図1について、実際にこの順で辿ると
   (1,1) → (1,2) → (1,3) → (1,4) → (1,5) → (2,5) で行き止まり。
   そこで (1,5) → (1,4) と戻り、 (1,3) → (2,3) で再び行き止まり。
   さらに (1,1) まで戻って右側へ伸ばし
   (2,1) → (3,1) → (3,2) → (4,2) → (4,3) → (4,4) → (5,4) → (5,5)
   となり、ここで終点に到達します。
4. この時点で“足跡フラグ”が付いた（＝訪問済み）マスは
   15 個〔上に挙げた座標列の重複を除いた集合〕です。
5. よって “訪問されなかった” 通過可能マスは
   19 − 15 ＝ 3 個 となります。

誤りやすいポイント

• 障害物・外壁を引いた後の可動マス総数を数え忘れる。
• 深さ優先探索では「終点に着いた瞬間」はまだ他の枝を探索していない点を見落とし、訪問マスを過大評価してしまう。
• 途中で同じマスに戻った回数を「訪問回数」に重ねて数えてしまう。問題では “同じマスを2回以上通ることはできない” と明示されている。

FAQ

解答の論理構成

1. 問題文の前提
   • 「(1,1)→(1,2)→(1,3)→(1,4)→(1,5)→(2,5)→(1,5)→(1,4)」の 7 回の“移動”後に「スタックには経過を示す4個の座標が格納されている」とある。
   • スタックに入るのは visit が呼ばれた直後であり、子ノードの探索終了後に stack_top ← ウ で 1 段階戻る（= ポップ動作）ことが分かる。
2. 7 回目の“移動”終了時点のスタック
   • 残っている座標は (1,1)、(1,2)、(1,3)、(1,4) の4個。
3. 8〜13 回目の“移動”を追う
   8. (1,4) → (1,3) へ“戻る” → (1,4) をポップ（残り3個）
   9. (1,3) → (2,3) へ“進む”  → (2,3) をプッシュ（4個）
   10. (2,3) → (1,3) へ“戻る” → (2,3) をポップ（3個）
   11. (1,3) → (1,2) へ“戻る” → (1,3) をポップ（2個）
   12. (1,2) → (1,1) へ“戻る” → (1,2) をポップ（1個）
   13. (1,1) → (2,1) へ“進む”  → (2,1) をプッシュ（2個）
4. 結論
   13 回目の“移動”後にスタックに残る座標は (1,1) と (2,1) の 2 個。
   よって ア は 2 となる。

誤りやすいポイント

• “移動”回数と visit 呼び出し回数を混同し、プッシュ／ポップのタイミングを取り違える。
• “戻る”動作でも“移動”回数が増えることを見落とし、8〜13 回目の流れを正しく数えられない。
• (1,2) から右方向 (2,2) へ進めると誤解（図1では障害物）。その結果スタック残数を多く見積もるミス。

FAQ

解答の論理構成

1. ゴールに到達したときの処理（イ）
   【問題文】には「終点にたどり着いた時点でスタックの内容を順番にたどると、それが解の一つになる。」とあります。また図3では
   for (k を 0 から stack_top まで 1 ずつ増やす) イ ← stack_visitk
   として、スタックに積まれた座標を“解を格納する配列”に写し取っています。解の番号は変数「sol_num」で管理しているので、行先は paths[sol_num]k しかありません。よって
   イ：paths[sol_num]k
2. 再帰呼び出し後のスタックポインタ復元（ウ）
   “進む”前に stack_top ← stack_top + 1 とインクリメントしているため、探索を終えて呼び出し元へ戻る直前で 1 つ減らして元の位置に戻す必要があります。したがって
   ウ：stack_top - 1
3. 足跡フラグの解除（エ）
   アルゴリズムの説明では「4方向いずれにも“進む”ことができないときには、現在いるマスのマス情報をOKフラグに戻し、一つ前のマスに“戻る”。」と述べられています。図3最後の行
   エ ← OK
   で、この“OK フラグに戻す”を実装しています。変更すべき対象は現在座標のマス情報、すなわち mazexy です。よって
   エ：mazexy

誤りやすいポイント

• イ で pathsk[sol_num] と添字を逆にしてしまう。第一添字が「解番号」、第二添字が「経路上の順番」と定義されています。
• ウ を stack_top のみで書き換え忘れ、再帰から戻るたびにポインタがずれ、スタックオーバーフローを招く。
• エ を VISITED に戻すと誤解し、いつまでも足跡が残ったままになり他の解が探索できなくなる。

FAQ

解答の論理構成

1. 変数の役割を確認
   • 表1に「“sol_num” は『見つけた解の総数』」と明記されています。
2. メイン処理の流れを追跡
   • 図4では stack_top ← 0 に続き sol_num ← 0 で初期化し、 その後 visit(start_x, start_y) を呼び出しています。
3. visit 関数での更新を確認
   • 図3の visit 内の終点判定部で sol_num ← sol_num + 1 が行われ、 迷路の解を発見するたびに “sol_num” が増加します。
4. if 条件の意図を読み取る
   • 図4の該当行は
     if( オ が 0 と等しい) “迷路の解は見つからなかった” と印字する
     ここで 0 かどうかを判定するのは「解が 1 つも見つからない場合」を検出するためです。
5. 結論
   • 解の総数を保持する “sol_num” こそが 0／非 0 を確認すべき変数なので、 オ に入る適切な字句は “sol_num” です。

誤りやすいポイント

• stack_top と混同する
  • スタックが空かどうかを判定する箇所と誤認しやすいですが、 ここで求められているのは「解の個数」です。
• visit が 1 回以上呼ばれた＝解があると早合点する
  • visit は探索自体を行うため、呼び出し回数と解の有無は直結しません。
• “paths[][]” のサイズで判断しようとする
  • 実際に格納されたかどうかは “sol_num” によって制御されており、 配列サイズはあらかじめ十分に確保されている前提です。

FAQ

解答の論理構成

1. 終点へ到達した後の動き
   【問題文】には「迷路の解を見つけた後も、他の解を見つけるために、終点から一つ前のマスに“戻り”、迷路の探索を続け、全ての探索を行ったら終了する。」とあります。したがって最初の解が見つかった直後、呼び出し元のマス（終点の一つ手前）へ制御が戻ります。
2. 最初の解が通る経路を確認
   方向優先順位は① y 座標を 1 増やす（北）→② x 座標を 1 増やす（東）→③ y 座標を 1 減らす（南）→④ x 座標を 1 減らす（西）です（【問題文】「“進む”は、現在いるマスから① … ④ …」）。
   図2（解が複数ある迷路）でこの優先順位どおりに深さ優先探索を行うと、最初に到達する終点までの経路は
   (1,1)→(1,2)→(1,3)→(2,3)→(3,3)→(3,4)→(4,4)→(5,4)→(5,5)
   となります。よって終点「(5,5)」の一つ前は「(5,4)」です。
3. “戻った”後の次の分岐点
   関数 visit の擬似コード（図3）の該当部分を引用します。

    if (maze<span class="choice-box">x</span>[y+1] が OK と等しい)
        visit(x, y+1)
    endif
    if (maze[x+1]<span class="choice-box">y</span> が OK と等しい)
        visit(x+1, y)
    endif
    if (maze<span class="choice-box">x</span>[y-1] が OK と等しい)
        visit(x, y-1)
    endif
    if (maze[x-1]<span class="choice-box">y</span> が OK と等しい)
        visit(x-1, y)
    endif
   

   (5,4) では
   ・北 (5,5)：すでに訪問済み（VISITED）
   ・東 (6,4)：外壁で NG
   ・南 (5,3)：OK
   ・西 (4,4)：VISITED
   となるため、最初に満たされる条件は南方向で visit(5,3) が呼び出されます。
4. よって、最初に実行される visit の引数は「5, 3」と確定します。

誤りやすいポイント

• 最初の解を「北へ行けるだけ進んで右端で下る」と早合点し、(1,5)→(2,5)…を正解経路と考えてしまう。図2では (3,5)、(4,5) が障害物で行き止まりです。
• 方向優先順位を東→南→西→北などと勘違いし、呼び出される座標を誤る。
• 終点から“戻る”際に足跡フラグが OK に戻る点を見落とし、(5,3) も VISITED のままだと思い込む。

FAQ

解答の論理構成

• 深さ優先探索では、常に
  「① y座標を1増やす→② x座標を1増やす→③ y座標を1減らす→④ x座標を1減らす」の順に“進む(visit を再帰呼出し)”ことが【問題文】に示されています。
• 一つ目の解が見つかった時点でスタックに残っている経路は
  (1,1)→(1,2)→(1,3)→(2,3)→(3,3)→(3,4)→(4,4)→(5,4)→(5,5)
  です（外れ枝であった(1,4)・(1,5)・(2,5) などは既に戻り済み）。
• 終点「(5,5)」から“戻る”と visit(5,4) に復帰し、 ③方向の探索で最初に呼び出される引数が「(5,3)」です（ここが設問中のカ）。
  ここを“基点”にして二つ目の解が見つかるまでの“移動”を以下に整理します。
  （進＝“進む”、戻＝“戻る”。移動のたびに移動先を“訪問”します。）

• 表より、基点「(5,3)」以降に発生した“移動”は全部で「22」回。
• その間に座標「(4,2)」が“訪問”された回数は「3」回。
• よって
  キ：22
  ク：3
  となります。

誤りやすいポイント

• “戻る”も【問題文】の「マスに“移動”したとき、移動先のマスを“訪問”した」という定義により 移動回数・訪問回数の両方に含まれる ことを忘れがちです。
• スタックから要素が抜けた時点でそのマスのフラグが「OK」に戻るため、同じマスを再度“進む”ことが可能になります。これを見落とすと訪問回数を 1 回少なく数えてしまいます。
• 方向選択の順序「①→②→③→④」を厳守しないと、経路の分岐点がずれ、移動総数も訪問回数も合いません。

FAQ