【情報】大学入学共通テスト過去問解説 情報関係基礎 2018年（平成30年）第３問 擬似言語プログラミング 迷路ゲーム【高校情報Ⅰ授業】
大学入学共通テスト「情報」過去問解説 情報関係基礎 2018年（平成30年）第３問
【資料ダウンロード】
PDFの他、パワーポイント、学習指導案 等の原本も無料提供しています。
情報教育の底上げが目的なので、資料を修正して、学校・塾（営利目的含む）の授業等で利用して頂いて問題ありません。私への連絡不要ですが、利用する際には、YouTubeチャンネル・情報Ⅰ動画教科書・IT用語動画辞典を紹介してもらえると嬉しいです。
■独自解説パワーポイント
https://toppakou.com/info1/download/98_大学入学共通テスト/04_H30_2018/情報大学入学共通テスト対策【情報関係基礎_平成30年(2018年)大問３】.pptx
■問題
大学入試センター 情報関係基礎過去問ダウンロード（情報処理学会 情報入試委員会）
https://drive.google.com/drive/folders/140pQJOKWzYH2-NvzPCyQdqFPHcZhCSOa
【文字おこし】
大学入学共通テスト 情報対策講座
情報関係基礎 ２０１８年（平成３０年）の大問３の擬似言語を使った迷路ゲームのプログラミング問題解説をしていきます。
白マスの道、黒マスの壁で構成された、図１の様な迷路があります。
図２は、袋小路を黒く塗って、Sと書かれたスタートからGと書かれたゴールまでの道を白いマスとして浮き出しています。塗ったマスは分かりやすくするためにグレーの色を使っています。
今回は、色々な迷路について袋小路を黒く塗る手順を考えていきます。
図３で考慮しない道の例が３つ示されています。
まずはこのような、環状になった道
そして２×２以上の道、
孤立した道 については考慮しない道になります。
１つのマスを座標ｘ、ｙを用いて マスｘ、ｙで表します。
図１の例ではスタートはマス（４，１） ゴールはマス（８、９）にあることになります。
では、問１部分に入っていきます。
道のマスで、この部分のように上下左右のうち三方が壁であるものを行き止まりと呼びます。
行き止まりのマスは、袋小路の先端で、黒く塗ることができます。塗ったマスは分かりやすいように黒ではなく、グレーを使います。
１つのマスを黒く塗ったことで、壁が発生するので、この部分のように隣接するますが新たに行き止まりになることがあります。
このように新たにできたものも含めて、すべての行き止まりを見つけて塗ることで、袋小路を塗ることができます。
手順はステップ１とステップ２があります。
ステップ１は外周を除く領域、図１では ２列２行目から１０列８行目のこの範囲について、上の行から下の行に各行のマスを左から右の順に行き止まりかどうかを調べていきます。
もし行き止まりであれば、黒にします。最後のマスまで調べたら、ステップ２に行きます。
ステップ２は ステップ１で１マスも塗られてなかったら手順を終了して、そうでなければステップ１に戻ります。
実際にシミュレーションを行いながら、問題を解いて行きます。
まず、２列２行目の判定を行います。３方向が壁なので、黒く塗って壁にします。
つぎは３列２行目はすでに壁で黒なので次の４列２行目の判定に移ります。
ここは２方向が壁で２方向が道なので行き止まりには該当しない為、白のままとします。
つぎは５列２行目はすでに壁で黒なので次の６列２行目の判定に移ります。
３方向が壁なので、黒く塗って壁にします。
次の７列２行目は先ほど黒く塗った部分で行き止まりになっているので、黒く塗りつぶします。
つぎは８列２行目はすでに壁で黒なので次の９列２行目の判定に移ります。
２方向が壁で２方向が道なので行き止まりには該当しない為、白のままとします。
次の１０列２行目は３方向が壁なので、黒く塗って壁にします。
折り返して次は２列３行目の判定になります。先ほど塗りつぶした部分を合わせて３方向かべなので、黒く塗りつぶします。
ここからは判定処理をアニメーションで最後まで流します。ただ、既に黒（グレー含む）の部分の判定も本来は行いますが、冗長で時間もかかるため、アニメーション上は判定をスキップしています。
―――
１回目の判定が終わりましたので、ここで該当する空欄部分を見ていきましょう。
まず最初に見つかる行き止まりのマスは２列２行目でした。
そして空欄アイは２列２行目の次に塗られる行き止まりの位置になります。
さきほどのアニメーションのとおり６列２行目になります。
そして７列３行目の次に塗るマスが空欄ウエになります。
さきほどのアニメーションのとおり２列４行目となります。
そして、空欄オカの１回目のステップ１で最後に塗られるマスは、この部分なので７列８行目となります。
そして最後の１０列８行目まで来たらステップ２に移り、１つ以上黒く塗ったマスがあるので、２回目に入ります。
これもアニメーションを流していきます。
ただ、すでに黒やグレーの部分の判定も本来は行いますが、冗長で時間がかかるためアニメーション上は省略します。
最後まで判定し終わったので、２回目の判定に関する問題を確認していきましょう。
空欄キは２回目のステップ１で塗られるマスの総数が問われています。
この薄いグレー部分を数えると３個なので空欄キは３になります。
―――
３回目に入ります。これも先ほどと同じように既に黒の部分は省略した判定アニメーションを先に見ていきます。
空欄ク、ケは３回目で初めに行きどまるマスについて問われています。
先ほどのアニメーションのとおりこの部分が該当するので、列を表す空欄クは３、行を表す空欄ケは８になります。
４回目のアニメーションも見ていきましょう。
１か所だけが塗られました。
５回目のアニメーションも見ていきましょう。
これも１か所だけが塗られました。
６回目のアニメーションも見ていきましょう。
これも１か所だけが塗られました。
７回目のアニメーションも見ていきましょう。
一つも塗られなかったので、これで全ての手順が終了します。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
では、問２の擬似言語問題を解いて行きましょう。
先ほどの迷路を ２次元配列Masuに格納します。
理解しやすいように色も付けておきます
壁の場合は１、道の場合は０ スタートかゴールなら９を代入します。
例えば、１行１列目は壁なので、１が設定されています。
擬似言語の１行目から１１行目は、先ほどのマスごとの行き止まり判定をおこない、行き止まりならMasu配列の該当部分に１つまり壁を設定します。
１２行目から２１行目までは、壁を黒マス、道およびスタートとゴールを白マスとして迷路を表示する処理になります。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
１１行目までの処理に空欄がありますので、実際に値を当てはめながら処理を説明していきます。
２行目は 変数nuttaに 空欄コの値を代入しています。
１１行目を見ると nuttaが ０になるまで実行するとありますので、０になったら、つまり行き止まりで黒く塗るマスが無くなったらループを抜けることができます。
７行目でnuttaを１に更新する処理があります。塗った実績があればループを継続する必要があるため１を設定しています。
塗らなかった場合の０にする処理が無いので２行目は初期値として０を入れる処理と考えられます。
よって空欄コは０となります。
３行目は 行であるｙ軸のループ条件となります。Ｙ＝２から空欄サまで１ずつ増やしながらとあります。先ほどの通り外枠は対象外とするので、この図で言うと９―１でyが８になるまで繰り返します。
本文にあるように、迷路の行数は変数tateに格納されているので、変数を使うとtate-1となり、選択肢としては⑥が該当します。
４行目は 列であるｘ軸のループ条件となります。Ｘ＝２から空欄シまで１ずつ増やしながらとあります。先ほどの通り外枠は対象外とするので、この図で言うと１１―１でｘが１０になるまで繰り返します。
本文にあるように、迷路の列数は変数yokoに格納されているので、変数を使うとyoko-1となり、選択肢としては⑦が該当します。
５行目は上下左右のマスの値を全て足して変数ｓに代入しています。
６行目を見ると、マス目を塗りつぶす条件としているので、行き止まりかどうかの判定になります。
つまり３方向が壁の場合は上下左右の値を足すと３になるので空欄セは３になります。
空欄スは今のマスが白つまり、０の場合塗りつぶす必要があるので
Masu[x,y]=0 となり選択肢としては②となります。
７行目は黒く塗りつぶす処理なので 空欄ソは１になります。
何パターンかシミュレーションしていきましょう。
★２列２行
ｘが２ yが２ の時の判定を行っていきます。
Masu[２－１、２]は左側のマスなので１となります
Masu[2+1,2]は右側のマスなので１となります。
Masu[2,2-1]は上側のマスなので１となります。
Masu[2,2+1]は下側のマスなので０となります。
全て足すと３になります。
今いるマスが０ かつ sが３なので
今いるMasu[2,2]に１を代入します。
★４列２行
ｘが４ yが２ の時の判定を行っていきます。
Masu[４－１、２]は左側のマスなので１となります
Masu[４+1,2]は右側のマスなので１となります。
Masu[４,2-1]は上側のマスなので９となります。
Masu[４,2+1]は下側のマスなので０となります。
全て足すと１１になり、s=3ではないので、塗りつぶし処理は行いません。
★２列３行
ｘが２ yが３ の時の判定を行っていきます。
Masu[２－１、３]は左側のマスなので１となります
Masu[2+1,３]は右側のマスなので１となります。
Masu[2,3-1]は上側のマスで先ほど黒く塗ったマスなので１となります。
Masu[2,3+1]は下側のマスなので０となります。
全て足すと３になります。
今いるマスが０ かつ sが３なので
今いるMasu[2,3]に１を代入します。
この処理を各マス繰り返していきます。
――――
続けて問３の解説をしていきます。
先ほど説明した手順は、袋小路を塗り終わるまで何度もステップ１を繰り返さなければならず、非効率でした。
手順２では行き止まりを見付けたら、その分岐点に到達するまで新たにできた行き止まりを連続して塗る方法になります。
ステップ１は先ほどと同じように外周を除く領域について、上の行から下の行に、各行のマスを左から右の順に着目します。
ステップ２は着目したマスが行き止まりであればそのマスを塗り、ステップ３に進み、そうでなければステップ１を再開します。
ステップ３は着目したマスの上下左右に隣接するマスうち、あらたに行き止まりになった可能性のあるマスに着目し、ステップ２に進みます。
実際にシミュレーションしていきます。
まず、はじめの２列２行目は行き止まりなので塗りつぶします。先ほどの手順１では直ぐに右の判定にうつりましたが、今回は行き止まりだったので、隣接するマス目で白色のマス目に着目します。今回は下のマス目になります。そして、これも行き止まりになるので塗りつぶします。
さらに下のマス目に着目しこれも行き止まりなので、塗りつぶします。
つぎはその右隣のマスに注目しこれは、行き止まりではないので白のままとなります。
ここでステップ１に戻ります。つまり２列２行の判定をしていたので、その右の判定を行います。
では、最後までアニメーションを走らせていきます。
すでに黒い部分も判定しますが、冗長なのでアニメーション上は省略しています。
このように１回目の処理で必要なマスを全て塗りつぶせたので非常に効率的なやりかたとなります。
今説明した処理を擬似言語で見ていきます。
先に空欄部分は正答を表示させておきます。実際に数値を当てはめながら変数がどのように変化するかを理解していきましょう。
１行目と２行目は先ほどと同じで上の行から下の行に判定するために、Yを２から増やして、同じ行でxを１ずつ増やしていく処理になります。
3行目はｘの値をiに代入します。yの値をｊに代入します。
敢えて他の変数に入れているのは、隣接する道を判定する際に、行き止まりでなくなった場合に、元々の判定箇所に戻る場所を保持しておくためになります。
４行目は、白マス判定と行き止まり判定、ループの継続条件になります。
行き止まりの場合に、５行目から８行目の処理が繰り返し行われれます。
５行目は今いるマスを壁にするために、１を設定しています。
６行目から７行目について
今回は縦横方向の増減値のdiとdjの変数が追加になっています。
一言で言えば、行き止まりになった時に次はどの方向を見ればいいかを保持します。
例えば、左側のマスが白つまり０の時は、横方向の増減値であるdiはー１になるためdiはー１となります。
右側のマスが白つまり０の時は 横方向の増減値は＋１になるためdiは１になります。
このdiの値を求める場合は、今いる場所の左側のマスの値―右側のマスの値で求めることができます。
上側のマスが白つまり０の時は 縦方向の増減値はー１になるためdjはー１になります。
下側のマスが白の時は、下方向の増減値であるdjは+１になるためdjは+１となります。
このdjの値を求める場合は、今いる場所の上側のマスの値―下側のマスの値で求めることができます。
８行目について i←i+di は次に見る横方向のマス座標をiに代入しています。
j←j+djは次に見る縦方向のマス座標をjに代入しています。
では、何パターンか数値を当てはめながら説明していきます。
２列２行目の判定を行っています。
３行目でｘは２なのでiにも２が代入されます。
ｙも２なのでｊにも２が代入されます。
４行目でマスが０で上下左右の合計が３なのでＴｒｕｅとなりループ処理に入ります。
５行目で今いるマスに１を設定し壁にします。
６行目は左マスは１、右マスは１ なので引き算をして ０がdiに代入されます。
７行目は上マスは１ 下マスは０ なので引き算をして １がdjに代入されます。
８行目の i+diは２＋０で ２がiに代入されます
j+djは ２＋１なので ３がjに代入されます。
ループ処理で下マスの２列３行目の判定を行っています。
４行目でマスが０で上下左右の合計が３なのでＴｒｕｅとなりループ処理に入ります。
５行目で今いるマスに１を設定し壁にします。
６行目は左マスは１、右マスは１ なので引き算をして ０がdiに代入されます。
７行目は上マスは１ 下マスは０ なので引き算をして １がdjに代入されます。
８行目の i+diは２＋０で ２がiに代入されます
j+djは ３＋１なので ４がjに代入されます。
ループ処理で下マスの２列４行目の判定を行っています。
４行目でマスが０で上下左右の合計が３なのでＴｒｕｅとなりループ処理に入ります。
５行目で今いるマスに１を設定し壁にします。
６行目は左マスは１、右マスは０ なので引き算をして １がdiに代入されます。
７行目は上マスは１ 下マスは１ なので引き算をして ０がdjに代入されます。
８行目の i+diは２＋１で ３がiに代入されます
j+djは ４＋０なので ４がjに代入されます。
つぎの３列４行目の判定は上下左右の合計は２なのでループの継続条件に合致しません。
２行目の親ループに戻り、２列２行目から右隣の３列２行目の判定処理を行います。
このような流れを繰り返すことで効率的に行き止まりを判定することができます。
今回の解説は以上になります。
最後までご視聴ありがとうございました。
【参考サイト・参考文献】
大学入試センター 情報関係基礎過去問ダウンロード（情報処理学会 情報入試委員会）
https://drive.google.com/drive/folders/140pQJOKWzYH2-NvzPCyQdqFPHcZhCSOa
tkmium note 難関進学校の情報科教諭が作成
【解説】 情報関係基礎 平成30年度 センター試験 2018 | ページ 3 | tkmium-note
https://tkmium.tech/jouhoukankei-h30/3/
E.V.ジュニア note 難関進学校の数学科・情報科教諭が作成
マガジン「プログラミング教育」総目次｜E.V.ジュニア｜note
https://note.com/evjunior/n/ne5610edd5f37
【YouTubeチャンネル】
https://www.youtube.com/c/toppakou
【IT用語動画辞典】
https://toppakou.com/ITWORD/
【解説重要用語】
擬似言語、変数、配列
★私の目標
「とある男が授業をしてみた」 の葉一さん
https://www.youtube.com/user/toaruotokohaichi
※Google社に招待頂いた、「YouTube教育クリエイターサミット2020」で
葉一さんと文部科学省・Google役員の対談セッションに感銘を受けて、高校情報講座スタートしています。
この記事が気に入ったらサポートをしてみませんか？