【C#】BFS(幅優先探索)でグリッド状のマップを経路探索する際に、元のマップ情報に変更を加えないで処理する方法

はじめに

本記事のテーマ

BFSを使用して、グリッド状で与えられるマップにおいて、始点→終点へのホップ数を計算す際に、通過済みのマスは元のマップ情報に書き込むような処理を入れていたのですが、それだと不都合がでるケースが発生したので、元のマップ情報を修正しないでもいいような実装に修正しました。(前提で記載しますが、"."のマスを通過した際に"#"に書き換えるという処理です)

ちなみに、過去に実装したBFSをベースに記事にしているので前の記事を見ないと主旨がわかりにくいと思いますが、ご容赦ください。。

過去リンク

過去、BFSについて言及した記事です。下記リンクの実装でも問題はないのですが、その実装だと不都合が発生した部分があったのでその点について実装を修正しました。 c-taquna.hatenablog.com

今回の前提

下記がインプットで与えられるものとします

• 始点は sx, syで与えられる
• 終点は gx, gyで与えられる
• ma情報はchar[,]の二次元配列で与えられる(" . " が通れるマス、" # " が通れないマス)

本題

以前の実装でみつかった課題について

• BFSの実装で、一度通過したマスを " # "に置き換えるという処理を入れていたが、始点が何パターンかある場合、毎回mapを最新状態に戻す必要があり、実装が複雑かつ計算量の増加の要因となっていた

これを下記のように改善しました。

• BFSの処理の最初に、始点から各マスへの距離を格納するための二次元配列を作成しておき、マスターとなるマップの状態ではなく、その距離の配列の値を使用してマスが通過済みかどうかを判断する

下記は、初期化ですべてのマスに -1 を入れておいて、 -1 だったらまだ未通過であると判断できるようにしています。

int[,] dist = new int[X, Y];
for (int y = 0; y < Y; y++)
{
    for (int x = 0; x < X; x++)
    {
        dist[x, y] = -1;
    }
}

実装

実装の全体像を載せておきます。

static int X;
static int Y;
static int GridBFS(int sx, int sy, int gx, int gy, char[,] map)
{
    int[,] dist = new int[X, Y];
    for (int y = 0; y < Y; y++)
    {
        for (int x = 0; x < X; x++)
        {
            dist[x, y] = -1;
        }
    }
    Queue<Tuple<int, int, int>> tq = new Queue<Tuple<int, int, int>>();
    int step = 0;
    tq.Enqueue(Tuple.Create(sx, sy, step));
    dist[sx, sy] = 0;
    int[] vx = { 0, 1, 0, -1 };
    int[] vy = { 1, 0, -1, 0 };
    while (0 < tq.Count)
    {
        var q = tq.Dequeue();
        int x = q.Item1;
        int y = q.Item2;
        step = q.Item3;

        if (x == gx && y == gy) break;
        for (int i = 0; i < 4; i++)
        {
            int nx = x + vx[i];
            int ny = y + vy[i];
            if ((0 <= nx && nx < X) && (0 <= ny && ny < Y) && map[nx, ny] == '.' && dist[nx, ny] == -1)
            {
                dist[nx, ny] = dist[x, y] + 1;
                tq.Enqueue(Tuple.Create(nx, ny, step + 1));
            }
        }
    }
    return step; 
}

結論

• BFSの処理を行う際に、始点からの距離情報を格納する配列を作成し(すべての初期値は -1 にしておく)、次に進むマスの値が-1じゃなければ未通過と判断するロジックにする

別記事で各つもりですが、今回はAtCoder Begginer Contest 151D 問題にて反省があったので、BFSの実装を修正してみました。