【AtCoder】【C#】幅優先探索の実装~その②~ AtCoder Beginner Contest 007 C問題より
以前、下記記事でも書いたように幅優先探索を実装しました。題材として、AtCoderの問題を使用しました。ですが、結果はほぼTLEにて終了。当時は原因がわからず放置していたのですが、蟻本で再度、幅優先探索について勉強する機会ができたので、あらためて前回の課題部分を解決した実装をしてみました。
この記事の主題は、主にC#における幅優先探索実装の一例の紹介です。基本的には幅優先探索のアルゴリズムは理解している上で話しを進めています。
はじめに
幅優先探索の実装の説明に入る前に、前回の記事について簡単にまとめておきます。
問題へのリンク
問題へのリンクを張っておきます。 atcoder.jp
過去の記事について
過去記事のリンクは最初の方に張ってあるので、そちらを参照してください。
前回記事の課題について
まず、問題となったのは最初の2ケース以外TLEになっていることです。最初の2ケースはうまくいっているので、計算量に問題があるものと考えられます。この計算量がなぜ多くなっているのか、どうやって減らすのかが今回の問題でした。
本論
前回の課題で問題となった点と、その解決方法
今回、問題だったのは一度経由した点の処理をしていなかったことが問題でした。当時はアルゴリズムの勉強を始めたばかりだったので(という言い訳、、)、今となってな当たり前な処理ができていませんでした。
今回、壁が "#"で経由できる点が"."で与えられます。今回の実装は次の点の候補が"."だったらさらにそこから4方向を調べるといったものでした。下記のような感じで書いていました。
if (次のマス == '.') { q.Enqueue(Tuple.Create(次のマスのx, 次のマスのy, 今まで経由したマス + 1)); }
ただ、これだと何度も同じマスが調べられてしまうので、一度経由したマスは#に変更するようにしました。
if (次のマス == '.') { 次のマス = '#'; q.Enqueue(Tuple.Create(次のマスのx, 次のマスのy, 今まで経由したマス + 1)); }
これで一度経由されたマスはもう計算対象にならないので計算量がぐっと減らせます。この実装で気をつけたいのはキューに入れる前に#で埋めないといけないという点ですね。
実装
上記の実装で前回の問題は解決できたのですが、下記実装のメモをあわせて残しておこうと思います。
Tupleの使用
複数の値をまとめてキューに入れたい時は、Tupleのキューを作成して入れると良いと思います。こんな感じです。
Queue<Tuple<int, int, int>> tq = new Queue<Tuple<int, int, int>>(); q.Enqueue(Tuple.Create(次のマスのx, 次のマスのy, 今まで経由したマス + 1));
各マスの周辺を調べる時の実装方法
あるマスから、四方のマスを確認する時の実装です。下記のようにやるときれいに書けます。
int[] vx = { 0, 1, 0, -1 }; int[] vy = { 1, 0, -1, 0 }; for (int i = 0; i < 4; i++) { int nx = x + vx[i]; int ny = y + vy[i]; if ((0 <= nx && nx < C) && (0 <= ny && ny < R) && map[nx, ny] == '.') { map[nx, ny] = '#'; tq.Enqueue(Tuple.Create(nx, ny, step + 1)); } }
【AtCoder】【C#】DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選 の反省
ここでは、DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選(以下、DDCC)のコンテンストに参加して、どのように考え解いたのか、なぜ解けたのか、なぜ解けなかったのかを反省として書き残しておきたいと思います。
続きを読む【C#】 第二回全国統一プログラミング王決定戦予選 の反省
最近コンテストに参加しても反省ができていなかったのと、今回は解法までわかったが、実装がうまくいかず解けなかった問題があるので、忘れないように反省メモを残しておきます。完全自分用メモです。
続きを読む