R4秋季 応用情報午後プログラミング「迷路」をPythonでコーディングしてみた!

最近は、アルバイトや資格試験、学会発表等多忙を極めていましたのでなかなか投稿が難しく、気づけばもう冬目前ですね。
ようやく、普通の日常が戻ってきたので就活が始まる3月くらいまでは趣味程度にブログ更新していこうかなと考えております。
では本題。
皆さんは10月9日にあった応用情報技術者試験、受験しましたか? 当ブログでも度々取り上げてきた「応用情報技術者試験」ですが、春期試験を逃した(予約忘れ)僕は満を持して秋季試験を受験してまいりました。
正直、手ごたえは微妙。。。
今回は例年に比べてやや易化していたような気もしますが、普段解いていた分野を避けて別の分野を解いてしまったことが要因でしょうか。
まあ、そんなことはさておき、来月辺りから諸事情でプログラミング言語のPythonを扱う予定があってですね、その練習がてら応用情報技術者試験 午後問題3の「プログラミング」をコーディングしてみよう!ということでコーディングしてみたので記録として残しておきます。

問題内容
問題分は長くなるので端的にまとめておきますね。
問3 迷路の探索処理について
・n×mの2次元マス(迷路)を用意し、始点と終点を決めてその解路を全て見つける。
・迷路内には障害物マスが存在し、そのマスに移動することはできない。
・また、”移動”には”進む”と”戻る”の2種類存在する。 障害物マスにはNGフラグ、それ以外にはOKフラグを立て、”進む”はOKフラグが立っているマスにしか進めない。
・”進む”処理を行った場合は現在いるマスに足跡フラグを立てる。
・”進む”処理には①y座標を1増やす、②x座標を1増やす、③y座標を1減らす、④x座標を1減らすの4種類存在し、①②③④の順に実行する。
・”進む”ことができない場合には”戻る”処理を行う。
・”戻る”処理は”進んで”きた1つ前のマスに動くことで、今いるマスのフラグをOKフラグに戻してから移動する。
以上を再帰的に行う。
といった感じです。(間違ってたらすみません)
詳しくは過去問をご覧ください!(R4 10/30現在ではまだ過去問の公開はされていないようです)
プログラムコード
ではプログラムを書いていきます。
ライブラリのインポート
import matplotlib.pyplot as plt
import matplotlib.patches as pat
問題にはありませんが、迷路を表示したいのでそれ用のライブラリです。
移動関数visitを作成
def visit(x, y):
global maze
global stack_top
global stack_visit
global paths
global sol_num
global way
maze[x][y]=VISITED
if (len(stack_visit) < stack_top+1):
stack_visit.append([x, y])
else:
stack_visit[stack_top]=[x, y]
if (x == goal_x and y == goal_y):
path=[]
for k in range(stack_top+1):
path.append(stack_visit[k])
#paths[sol_num]=stack_visit.copy()
paths[sol_num]=path.copy()# Pythonは変数参照型 .copyなしでは最終的なpathの値が全てに反映される
sol_num=sol_num+1
else:
stack_top=stack_top+1
if (maze[x][y+1] == OK):
visit(x,y+1)
if (maze[x+1][y] == OK):
visit(x+1,y)
if (maze[x][y-1] == OK):
visit(x,y-1)
if (maze[x-1][y] == OK):
visit(x-1,y)
stack_top=stack_top-1
maze[x][y]=OK
問題文とほとんど同じものになります。
注意点として、Pythonは変数参照型なので paths[sol_num]=path
ではなく、 paths[sol_num]=path.copy()
とします。
メインプログラム
maze=[[0 for i in range(5)] for j in range(5)]
stack_visit=[]
point_x=[]
point_y=[]
paths={}
stack_top=0
sol_num=0
OK=1
NG=2
VISITED=3
#枠以外の好きな部分を適宜変更
maze[0][0]=NG
maze[0][1]=NG
maze[0][2]=NG
maze[0][3]=NG
maze[0][4]=NG
maze[1][0]=NG
maze[1][1]=OK
maze[1][2]=OK
maze[1][3]=OK
maze[1][4]=NG
maze[2][0]=NG
maze[2][1]=OK
maze[2][2]=OK
maze[2][3]=OK
maze[2][4]=NG
maze[3][0]=NG
maze[3][1]=OK
maze[3][2]=NG
maze[3][3]=OK
maze[3][4]=NG
maze[4][0]=NG
maze[4][1]=NG
maze[4][2]=NG
maze[4][3]=NG
maze[4][4]=NG
#始点と終点
start_x=1
start_y=1
goal_x=3
goal_y=3
#探索開始
visit(start_x,start_y)
#解を表示
if (sol_num == 0):
print("no maze")
else:
for num in range(sol_num):
print("解" + str(num+1) + "=" + str(paths[num]))
#迷路を作成
x = [0,0.2,0.4,0.6,0.8]
y = [0,0.2,0.4,0.6,0.8]
for num in range(sol_num):
path_len=len(paths[num])
point_x=[]
point_y=[]
#解路の座標
for i in range(path_len):
point_x.append( (float(paths[num][i][0])+float(paths[num][i][0])+1.0)*0.1 )
point_y.append( (float(paths[num][i][1])+float(paths[num][i][1])+1.0)*0.1 )
fig = plt.figure(figsize=(5, 5))
ax = fig.add_subplot(111)
for k in range(5):
for i in range(5):
#適宜変更(障壁個所)
if(x[k] == 0 or x[k] == 0.8 or y[i] == 0 or y[i] == 0.8 or (x[k] == 0.6 and y[i] == 0.4)):
rec = pat.Rectangle(xy = (x[k], y[i]), width = 0.2, height = 0.2,
angle = 0, color = "black")
ax.add_patch(rec)
else:
rec = pat.Rectangle(xy = (x[k], y[i]), width = 0.2, height = 0.2, fill=False, angle = 0, color = "black")
ax.add_patch(rec)
plt.plot(point_x, point_y, "-", linewidth=2, label="解路")
plt.plot(point_x[0], point_y[0], "D", color="red")
plt.plot(point_x[path_len-1], point_y[path_len-1], "x", color="blue")
plt.show()
少し冗長的ですが、Python初心者なのでお許しを。。。
今回は5×5の迷路にしてみました。(処理量が多く、これ以上だとエラー吐かれました。。。)
そして、枠(maze[0][0~4]、maze[4][0~4]、maze[0~4][0]、maze[0~4][4])とmaze[3][2]を障害物マスとしています。
↑こんな感じ。
結果
解1=[[1, 1], [1, 2], [1, 3], [2, 3], [3, 3]]
解2=[[1, 1], [1, 2], [2, 2], [2, 3], [3, 3]]
解3=[[1, 1], [2, 1], [2, 2], [2, 3], [3, 3]]
解4=[[1, 1], [2, 1], [2, 2], [1, 2], [1, 3], [2, 3], [3, 3]]
うんうん。なんだか良さそうですね。
絵にして見てみると、、、
解1
解2
解3
解4
でけた!
まとめ
いかがだったでしょうか。
今回は応用情報技術者試験のプログラミング問題「迷路」をPythonで実装してみました。
実装してみた感想ですが、
・サンプルコードが問題文にあるのでコーディングが簡単
・要点が抑えられているので学習効率が良い
・言語独自の用法は自分で調べる必要がある
といった感じでしょうか。
結構楽しかったのでまた他の問題にもチャレンジしてみようかなと考えています!
では、最後まで読んで頂きありがとうございました!