大学入学共通テスト（情報） 過去問
令和7年度（2025年度）追・再試験
問21 (第2問 問11)

B　　次の文章を読み、後の問いに答えよ。

SさんとTさんは、迷路を使ったゲームを作ろうとしている。迷路は図1のようにマス目を壁（太線で表されている。）で区切って作る。キャラクターは、上下左右の入力操作を受け、その方向に壁がなければ隣接するマスに移動する。

次の文章を読み、空欄（　サ　）に入れるのに最も適当なものを、後の解答群のうちから一つ選べ。

迷路の表示とキャラクターの移動処理を実現するために、迷路のマスごとに一つの数を割り当てて迷路の構造を表現するような方法をSさん、Tさんがそれぞれ考えた。次は、そのときのSさんとTさんの会話である。

S：私は4ビットの2進表記で考えてみたよ（図2）。左端のビットから右側に向かって、マス目の上下左右に対して左→上→右→下の順で、壁がある場合は1，壁がない場合は0が並ぶような表現にしたんだ。
T：その場合、一つの壁の有無の情報が二つのマスで重複していて無駄じゃない？例えば、図2のXのマスの左端から4ビット目と、Yのマスの左端から（　ク　）ビット目は同じ壁の有無を表してるよね。私の方法（図3）も2進表記だけど、それぞれのマスごとに、左と上だけ、壁があるかどうかを表すようにしたんだ。仮想的なマス目を、右と下に一列ずつ余分にくっつけて表現する必要はあるけど。
S：なるほど。確かに重複はなくなったけど、キャラクターが移動できるかどうかの判断がやりにくくない？図2だと右に移動できるかどうかはすぐわかるけど、図3ではどうする？
T：（　ケ　）なら右に壁がある、ってわかるけど、確かに難しくなったね。
S：迷路全体を表すのに必要なデータ量はどっちが小さくなるのかな。元の迷路がN×Nマスでできているとき、迷路全体を表すために、私の方法（図2）では（　コ　）ビット、Tさんの方法（図3）では（　サ　）ビットが必要になるってことか。Tさんの方法の方が必要なデータ量が少なくなるのは、N＞（　シ　）のときだね。