2019-11-30

【AtCoder】【C#】グラフ問題でのノード同士の接続状態の管理、経路問題での通過したノードを管理する方法の紹介

C# アルゴリズムプログラミング AtCoder

今回のタイトルですが、題材となっているのは下記の問題です。

atcoder.jp

2019-11-27

【AtCoder】【C#】幅優先探索の実装~その②~　AtCoder Beginner Contest 007 C問題より

AtCoder C# アルゴリズムプログラミング

はじめに
- 問題へのリンク
- 過去の記事について
  - 前回記事の課題について
本論
- 前回の課題で問題となった点と、その解決方法
- 実装
  - Tupleの使用
  - 各マスの周辺を調べる時の実装方法

以前、下記記事でも書いたように幅優先探索を実装しました。題材として、AtCoderの問題を使用しました。ですが、結果はほぼTLEにて終了。当時は原因がわからず放置していたのですが、蟻本で再度、幅優先探索について勉強する機会ができたので、あらためて前回の課題部分を解決した実装をしてみました。

この記事の主題は、主にC#における幅優先探索実装の一例の紹介です。基本的には幅優先探索のアルゴリズムは理解している上で話しを進めています。

c-taquna.hatenablog.com

はじめに

幅優先探索の実装の説明に入る前に、前回の記事について簡単にまとめておきます。

問題へのリンク

問題へのリンクを張っておきます。 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));
    }
}