令和7年度 春期 応用情報技術者試験 午後 問3 幅優先探索によるスライドパズルの解法

正解の根拠

スライドパズルの盤面（図2中の②）を、図3に示された2次元配列の形式に則って記述する問題です。
盤面の各行はそれぞれひとつの配列として中括弧 $\{\}$ で囲まれ、それらをさらに全体の中括弧で囲む必要があります。
図2中の②の盤面は上から順に以下のようになっています。

1. 1行目: 8, 6, 7
2. 2行目: 2, 9, 4
3. 3行目: 3, 5, 1
   これらを指定の構文に従って記述すると、 $\{\{8, 6, 7\}, \{2, 9, 4\}, \{3, 5, 1\}\}$ となります。

高得点のポイント

• 盤面の状態を各行ごとに正確に読み取っていること
• 指定された2次元配列の記述規則（中括弧の対応やカンマ区切りの構文）に厳密に従い記述できていること

正解の根拠

この空欄は、幅優先探索アルゴリズムにおけるメインループの継続（または終了）条件を決定する箇所です。
幅優先探索では、探索対象をキューに格納し、キューから要素を取り出しながら処理を進めます。探索が終了するのは、キューの中に探索すべき状態が存在しなくなったとき、すなわちキューが空になったときです。
プログラム中では、探索対象を格納するキューが explore_queue として定義されているため、キューが空であるかを判定するメソッドを用いた explore_queue.isEmpty() が入ります。

高得点のポイント

• 幅優先探索アルゴリズムの終了条件（キューが空になること）を正しく理解していること
• 利用する変数のスコープとオブジェクトのメソッド名を正確に記述できること

正解の根拠

キューからの要素の取り出し操作に関するメソッドを問う箇所です。
幅優先探索の反復処理内では、まずキューの先頭から探索対象の状態を1つ取り出し、それを基に次の状態を展開していきます。
キュー（Queue）のインターフェースにおいて、先頭要素を取得しつつ削除する標準的な操作は poll() または dequeue() などで行われます（言語仕様に依存しますが、本題の文脈に従います）。ここでは poll() が正解となります。

高得点のポイント

• キュー（Queue）の基本的なデータ構造とFIFO（先入れ先出し）の特性を理解していること
• 要素を取り出すための適切なメソッドを正確に記述できること

正解の根拠

空白マス（ゼロ）の移動処理において、移動量（変位）を取得するための配列参照箇所です。
移動方向および各方向に対する座標の増減は、2次元配列 direction に定義されています。ループ変数 i を用いて複数の方向を順に調べます。
インデックス 1 と 2 がそれぞれX方向やY方向の移動量を保持しているため、文脈に合わせて片方の移動量を取得する direction[i][1] が入ります。

高得点のポイント

• プログラム内で定義された2次元配列の構造を正しく理解していること
• ループ変数を用いた適切なインデックス指定（添字の記述）ができること

正解の根拠

空白マスが移動した先の座標が、盤面の範囲内に収まっているかを確認する境界チェック（バウンダリチェック）の条件式の一部です。
座標は 0 以上かつ盤面サイズ未満である必要があります。盤面サイズは変数 board_size によって管理されています。
したがって、移動後の座標値が超えてはならない上限値を示す board_size が入ります。

高得点のポイント

• 配列外参照等のエラーを防ぐための境界チェックの重要性を理解していること
• 条件式において上限判定に用いるべき変数を正確に特定できること

正解の根拠

ウと同様に、空白マスをもう一方の軸（X方向またはY方向）へ移動させる際の移動量を取得する記述です。
配列 direction において、一方の移動量がインデックス 1 にあるのに対し、もう一方はインデックス 2 に格納されています。
したがって、ループ変数 i と合わせて direction[i][2] が入ります。

高得点のポイント

• 多次元配列を用いたデータ管理と座標表現の仕組みを理解していること
• ウの記述と対になる適切な添字（インデックス）を正確に選択できること

正解の根拠

新しく生成された盤面状態が、最終的な目標状態（ゴール）に到達したかどうかを判定する処理です。
目標到達をチェックするための関数 checkGoal が用意されており、この関数は現在の盤面と目標とする盤面を比較します。
現在検証している新しい盤面は new_state.board、目標とする盤面は goal_board という変数に格納されているため、これらを引数として渡す checkGoal(new_state.board, goal_board) が正解となります。

高得点のポイント

• ゴール判定に必要なロジックと関数呼び出しの形式を正しく理解していること
• 引数として渡すべき適切なオブジェクトとそのプロパティを正確に指定できること

正解の根拠

新しく生成された状態が目標状態ではない場合、次以降の探索対象とするためにキューにその状態を追加する処理です。
探索待ちのキューに対する要素追加のメソッドは add() などが使用されます。
追加するべき要素は、新たに生成された状態を保持するオブジェクト new_state であるため、add(new_state) が正解となります。

高得点のポイント

• キューへの要素追加により探索空間を展開していく幅優先探索の流れを理解していること
• 探索キューで管理されるべきデータ型（状態オブジェクト全体）を正しく把握していること

正解の根拠

探索の過程において、同じ状態を何度も探索してしまうことを防ぐ（重複探索の防止）ために、訪問済みの状態を記録する処理です。
すでに訪れた盤面状態を管理するリストやセットに対し、現在の盤面を追加します。
状態オブジェクト全体ではなく、盤面の配置そのものを表すプロパティを記録するため、add(new_state.board) のような記述が入ります。

高得点のポイント

• 探索アルゴリズムにおける重複探索の防止（閉鎖リスト等への追加）の重要性を理解していること
• 訪問済みとして記録すべき適切なオブジェクトのプロパティを正確に指定できること