BFS(幅優先探索)ってなに？
皆さん、こんにちは！
ハリーです！競プロ精進日記の1週目になります。何から勉強を始めようか悩んだのですが、今週は、以前やろうと思ってやれていなかった BFS(幅優先探索) の勉強をしたいと思います。今回、BFS のアルゴリズムについて書こうと思ったのですが、私自身あまり理解していないことと、BFS についての解説記事が他にたくさんあったので今回は問題を解いていく過程記事に書かせていただきました。今回、BFS の問題を解いていくにあたって AtCoder Tags を使用させていただきました。このサイトでは、AtCoder の問題をカテゴリ別に分類してくれており、自分がやりたいカテゴリの問題を簡単に探すことが出来ます！もし、知らない方がいましたら是非使ってみてください！今回の記事は完全に自分のためのメモみたいになってます...。
C - 幅優先探索（AtCoder Beginner Contest 007）
1つ目の問題は、C - 幅優先探索という問題です。選択した理由は、問題の名前の通り BFS の基本となる問題だと思ったからです！それでは、解いていきましょう！
問題の概要
- 盤面のサイズと、迷路のスタート地点とゴール地点の座標が与えられます。
- それぞれのマスが通行可能な空きマス(
.)か通行不可能な壁マス(#)かという情報を持った盤面が与えられます。 - タート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着けるようになっています。
スタート地点からゴール地点に移動する最小手数を 行に出力する問題です。
最後に改行を忘れないこと！
入力例1
7 8
2 2
4 5
########
#......#
#.######
#..#...#
#..##..#
##.....#
########
出力例1
11
入力例2
5 8
2 2
2 4
########
#.#....#
#.###..#
#......#
########
出力例2
10
入力例3
50 50
2 2
49 49
##################################################
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
##################################################
出力例3
94
実装方法
まず問題文にも記載がありますが、幅優先探索ではキューというデータ構造を用いて以下の2つを行います。
- 追加(Push): キューの末尾にデータを追加する。
- 取り出し(Pop): キューの先頭のデータを取り出す。
上記の2つを行うために、collections ライブラリのimport を行います。
from collections import deque
次に入力を受け取ります。
まず、1行目で行数 $R(1\leq R \leq 50)$と列数 $C(1\leq C \leq 50)$を受け取ります。
r, c = map(int,input().split())
2行目でスタート地点の座標$(sy, sx)$、3行目でゴール地点の座標$(gy, gx)$を受け取ります。
sy, sx = map(int,input().split())
gy, gx = map(int,input().split())
4行目で $R$ 行、長さ $C$ の文字列を1行ずつ受け取ります。
grid = [list(input()) for _ in range(r)]
5行目以降で、盤面の情報を受け取ります。
grid = [list(input()) for _ in range(r)]
次に、受け取った座標のindex値をそろえるために、座標の値を$-1$します。
(sy, sx, gy, gx) = (sy - 1, sx - 1, gy - 1, gx - 1)
距離を保存するための配列を用意します。初期値として、各要素に $-1$ を入れます。
なぜ $-1$ を入れるかというと、距離が正の数であるため負の数で入れておくとまだ訪れていないことが表せるためです。
dist = [[-1] * c for _ in range(r)]
スタート地点はスタート地点から手数 $0$ でたどり着けるので、最短手数の $0$ を入れます。
dist[sy][sx] = 0
次は壁の判定を行います。# がある場合は、壁があるということなので壁用の値の $-2$ を入れます。
for i in range(r):
for j in range(c):
if grid[i][j] == "#":
dist[i][j] = -2
deque オブジェクトを生成します。生成したらスタート地点の座標を加えます。
q = deque()
q.append([sy, sx])
上下左右に対する変化量を決めます。
d = [[-1, 0], [1, 0], [0, -1], [0, 1]]
ここからが、BFS の主な処理になります。
まず while 文を作ります。while 文の中で初めにやるのが今いる地点の保存です。
v = q.popleft()
次に、今いる地点から上下左右を見ます。これは for 文で処理を行います。
for dy, dx in d:
次は、今いる地点から上下左右を見たときの地点が範囲内であるかどうかを if 文で調べます。範囲外だった場合は、無視して何も処理を行いません。
if not (0 <= v[0] + dy <= r - 1 and 0 <= v[1] + dx <= c - 1):
continue
次に、今いる地点から上下左右を見たときにその地点が訪れたことのある地点かどうかを if 文で調べます。各配列要素に初期値として $-1$ を入れているので、$-1$ ではなかった場合、その地点は1度訪れたことがある、または壁があるということになるので、無視して処理を行いません。
if dist[v[0] + dy][v[1] + dx] != -1:
continue
次に、距離の更新を行います。上記の2つの条件分岐を通過した場合、その地点は進むことができるということなので、今いる地点に $+1$ をして距離を更新してあげます。
dist[v[0] + dy][v[1] + dx] = dist[v[0]][v[1]] + 1
while 文の最後で、上記の条件分岐で訪れることができる地点がある場合は、新しい地点としてキューに追加してあげなければいけないので append で次の地点を配列 q に追加します。
q.append([v[0] + dy, v[1] + dx])
最後は、距離を保存した配列（dist） のゴール地点を出力すれば最小手数を出すことができます。
print(dist[gy][gx])
今までのコードをまとめると下記のようになります。
ACコード
from collections import deque
r, c = map(int,input().split())
sy, sx = map(int,input().split())
gy, gx = map(int,input().split())
grid = [list(input()) for _ in range(r)]
(sy, sx, gy, gx) = (sy - 1, sx - 1, gy - 1, gx - 1) # 0index
dist = [[-1] * c for _ in range(r)] # 距離を保存するための配列
dist[sy][sx] = 0 # スタート地点は０
# 壁の判定（distに壁用の数値を入れている）
for i in range(r):
for j in range(c):
if grid[i][j] == "#":
dist[i][j] = -2
q = deque()
q.append([sy, sx]) # スタート地点
d = [[-1, 0], [1, 0], [0, -1], [0, 1]] # 上下左右に対する変化量(y, x)
while q:
v = q.popleft() # 今いる場所(y, x)
for dy, dx in d: # 現在の地点から上下左右を見ている
if not (0 <= v[0] + dy <= r - 1 and 0 <= v[1] + dx <= c - 1): # 範囲外と壁は行かない
continue # 配列外参照
if dist[v[0] + dy][v[1] + dx] != -1: # 訪れたことがあるか壁の時は無視する
continue
dist[v[0] + dy][v[1] + dx] = dist[v[0]][v[1]] + 1 # 距離の更新
q.append([v[0] + dy, v[1] + dx]) # 新しくキューに追加する
print(dist[gy][gx])
最後に
以上が競プロ精進日記の1週目はBFS(幅優先探索) の練習記事でした！問題文が既に解説のような感じでしたね。BFS をやり始めた私にとっては、すごくためになる問題でした。さて、そろそろ今年も終わろうとしていますね。皆さんは今年どんな1年だったでしょうか？私は、単位に追われた1年でした...笑 後は夏のインターンシップで HTML と CSS に興味が湧いたので、今勉強中です！来年の春には入茶できるように頑張ります！
最後まで読んでいただいきありがとうございました！
なぜ競プロをサボるようになったのか？
自己紹介
皆さん、はじめまして！
Harry です。今回、競プロ Advent Calender 2021に参加させていただいたので、初めての記事を書かせていただきました！
私は1年ほど前に初めて競技プログラミング（以下競プロ）を始めました。そして、途中やっていなかった時期があり、本格的に始めたのが半年ほど前になります。現在（12/12）のAtCoder（競技プログラミングサイト）のRatingは191のバリバリの初心者です。使用している言語は、Pythonです。
何を書けばいいか悩んだ結果、初めての記事ということで、 AtCoder を始めたきっかけと、今までやってきたこと、そしてサボるようになってしまった原因について簡単に書きたいと思います。
なぜ競プロを始めたのか
私が競プロを始めたのは、友人から誘われたことがきっかけです。私の友人がAtCoder という競技プログラミングサイトをやっていたのは、時々耳にしていたのですが、ある日「一緒にやってみない？」と誘われました。私は高校の頃、情報処理科という学科に所属していたこともあり、プログラミングに苦手意識とかはなかったので、そこで初めて AtCoder でコンテストに出場しました。これが、私が競プロを始めたきっかけです。
今までやってきたこと
私が今まで主にやってきたことは下記の2つです。
- AtCoder Problems で過去の問題を解く
- なるべく毎週のコンテストに参加する
AtCoder Problemsで過去の問題を解く
私が競プロを始めてから主にやってきたことは、 AtCoder Problems というサイトを活用し、過去の AtCoder のコンテストで出題された問題を解くことです。
しかし、始めたばかりの私は過去問題のどの問題から解いていいのか分かりませんでした。そんな私のために @ryusuke__h さんが毎日 AtCoder Problems の Virtual Contests（以下バチャ）を開催してくれました。バチャ では毎回多くの人が参加してくださり、私も他の参加者に負けないように精一杯努力していました。
なるべく毎週のコンテストに参加する
AtCoder では、定期的にコンテストが開催されており初心者の私は、AtCoder Beginners Contest というコンテストに参加していました。そこでは、日々の精進の成果を出すことができ、レートも上がるので毎週の楽しみのひとつでした。
競プロをやっていて楽しかったこと
私が競プロをやっていて楽しかったことは以下の2つです。
- レーティング制度
- 頭を捻る問題を解くこと
レーティング制度
AtCoder には、レーティング制度があります。最近のゲームには、ランク制度やレーティング制度があるものが多く、私自身その制度がとても好きでした。なので、毎回コンテストに参加するときは、とても緊張していました。
頭を捻る問題を解くこと
普段の生活ではあまり頭を捻る（思考する）機会がないので、競プロはその機会として適していて、とても面白かったです。解けなかった問題でも、解説を見て「そんな考え方があったんだ！」と、いつも驚かされていました。
サボるようになった原因
これまでの内容を見ると、競プロを楽しんでいるように見え、サボるようになった理由が見当たらないと思います。私が、競プロをサボるようになったのは主にモチベーションの低下が原因です。そして、モチベーションの低下の原因となったとは以下の3つだと思います。
- 数学問題
- アルゴリズム
- 毎日の精進
数学問題
まず、サボるようになった原因の１つは数学問題が解けないことにあります。私は、高校で数学Ⅰと数学Ⅱの途中までしか履修しておらず、一般人よりも数学の知識はありませんでした。そのため、度々出題される数学問題を解くことが出来ず頭を悩ませていました。ちなみに、私は大学の必修科目である解析学を2回も落とし、今年3回目の履修をしています...。
アルゴリズム
2つ目の原因は、アルゴリズムです。プログラミングにはたくさんのアルゴリズムがあり、それを覚えなければ AtCoder のコンテストの問題を解くことができない場合が多くあります。なので、アルゴリズムを使えるようになることは必須でした。しかし、私自身がアルゴリズムに対して、あまり面白さを感じませんでした。また、ひとつのアルゴリズムを使えるようになるには、たくさん問題を解き練習をする必要があります。さらに、その成果はとても分かりずらいように感じました。私は、その地道な努力がとても苦手でした。（今まで学んだアルゴリズムは、累積和とbit全探索、Union-Find くらいです）
毎日の精進
私は競プロを始める前は、根っからのゲーマーでした。競プロを始める前の頃は、朝から講義を受講し、夜はゲームをやる or バイトにいく、のような感じでした。競プロを始めてからは、夜のゲームの時間を競プロの精進の時間にし、バイトが終わり次第バチャをやるという感じでした。そのため、競プロを始めた１ヵ月弱の間は全くゲームに触れていませんでした。始めたばかりの頃は、競プロを楽しんでいたのですが、日が経つにつれてゲームをやりたい欲が増していきました。私にとってゲームをできない日常は辛かったです。
競プロをやっていなかった間、何をしていたのか
主に、大学の課題とゲームの2つです。私の大学では、3年でプロジェクト学習というグループで研究や開発を行うカリキュラムがあります。その開発での私の仕事がなかなか終わらず、他のことに時間を使う余裕がありませんでした。「じゃあ、講義の間の時間は何してたの？」と思う方もいるかもしれません。愚かな私はその空いた時間をすべてゲームに費やしていました。今思えば、もったいない使い方をしていたなと思います。
最後に
私は競プロをサボっていましたが、決して嫌いになったわけではありません！最近では、なるべくコンテストに参加するように心がけていますし、新しいアルゴリズムも勉強中です。今ではアルゴリズムに面白さを感じるようになりました。前のように、毎日勉強を続けることは難しいですが、「自分なりのやり方でこれからも続けていこうと思います。」と書こうと思ったのですが、それだとまたサボってしまう気がしたので、ここでやることを宣言したいと思います。
来週から、1週間で学んだこと（アルゴリズム、問題解説）について記事をひとつずつではありますが、書いていこうと思います。そして、来年の春までには入茶目指して頑張ります！ちなみにもし書かなかった場合は、ペナルティを皆様に Twitter のアンケートで決めていただき、1番票が多かったペナルティを受けたいと思います。
ここまで読んでいただいた皆さまありがとうございました！初めての記事で読みづらいところが多々あったと思いますが、これから慣れていけるように頑張ります！
※本記事は競プロをサボるようになった原因の実体験を書いたものであり、決して競プロを批判するためのものではありません。不快な表現もあるかもしれませんがご容赦ください。
