【abc151-D】 幅優先探索(BFS)

※注意
この記事は、主に自分用に執筆したものです。ので、各所にお気持ちが伝わりづらい(伝わらない)言い回しやコードが散見されるかもしれませんがご了承ください。


#まえがき
[AtCoder Beginner Contest 151](https://atcoder.jp/contests/abc151)(後解き)。
A~Cは特に問題なく。Dは明らかにお勉強しなきゃなテーマだったけど、一旦無理やり思考で殴って通した(数時間かかってる)。たぶん我流が過ぎるのでこの場でひとつずつ頭の中を整理しよう。
※abc151-D(Maze Master).Difficulty: 927
本日のmain教科書↓
・[DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】](https://qiita.com/drken/items/4a7869c5e304883f539b)
・[DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】](https://qiita.com/drken/items/a803d4fc4a727e02f7ba)
・[BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜](https://qiita.com/drken/items/996d80bcae64649a6580)

BFSは「breadth-first search」らしいです


#あとがき
好き勝手記事を書きすぎたのと途中に鬼怒川温泉旅行+オケオールが挟まったせいでめちゃくちゃな仕上がりになった。ので注意喚起も兼ねて先にあとがきを置く。

BFSはたぶんなんとかなる。関係ないとこでよくわかんなかった事象がたくさんあるので、そっちがどこかで解決できたら嬉しいな


#本編
BFS、DFSの概要については、教科書がすごくわかりやすかったので確認したかったらそっち見よう。BFSはスタートに近い頂点から見ていくやつです。

とりあえずお勉強前に無理やり書いたやつ、後からor外から見たらめちゃめちゃ難解な気もするけど残しとく価値くらいありそうなのでとりまぶん投げる。コメントアウトの調整以外無加工。これ理解する必要があるとは思わないけどとりあえず自分の思考順に並べたかった。


##初見コード

```abc151/d2.cpp
#include <bits/stdc++.h>
using namespace std;

using Graph = vector<vector<int>>;

int bfs(const Graph& G, vector<bool>& seen, queue<int>& todo, int depth) {
    bool flag = true;
    while(!todo.empty()) {
        if(todo.front() == -1) {
            depth++;
            todo.pop();
            flag = true;
        }

        else {
            if(!seen[todo.front()]) {
                seen[todo.front()] = true;
                if(flag) {
                    todo.push(-1);
                    flag = false;
                }
                for(auto next_v : G[todo.front()]) {
                    if(seen[next_v]) continue;
                    todo.push(next_v);
                }
            }
            todo.pop();
        }
    }
    
    return depth;
}

int main() {
    int h,w;
    cin>>h>>w;
    vector<vector<char>> maze(h+2);

    //周りを壁で囲んでmaze作ってみた。あれ、悪くないのでは?
    for(int i=0; i<w+2; i++) maze[0].push_back('#');
    for(int i=1; i<=h; i++) {
        maze[i].push_back('#');
        for(int j=0; j<w; j++) {
            char s;
            cin>>s;
            maze[i].push_back(s);
        }
        maze[i].push_back('#');
    }
    for(int i=0; i<w+2; i++) maze[h+1].push_back('#');

    //グラフ入力作業
    Graph G(h*w+1);
    for(int i=1; i<=h; i++) {
        for(int j=1; j<=w; j++) {
            int posi = w*(i-1) + j;
            if(maze[i][j]=='.') {
                if(maze[i][j-1] == '.') G[posi].push_back(posi-1);
                if(maze[i-1][j] == '.') G[posi].push_back(posi-w);
                if(maze[i][j+1] == '.') G[posi].push_back(posi+1);
                if(maze[i+1][j] == '.') G[posi].push_back(posi+w);
            }
        }
    }

    //色々用意してforでbfsを道の数だけ回す
    vector<bool> seen;
    seen.assign(h*w+1, false);
    queue<int> todo;

    vector<int> proponent;
    for(int i=1; i<=h; i++) {
        for(int j=1; j<=w; j++) {
            if(maze[i][j]=='.') {
                int start = w*(i-1)+j;
                seen[start] = true;
                for(auto next : G[start]) {
                    todo.push(next);
                }
                int a = bfs(G, seen, todo, 0);
                proponent.push_back(a);
                seen.assign(h*w+1, false);
            }
        }
    }

    int ans = *max_element(proponent.begin(), proponent.end());

    cout<<ans<<endl;

    return 0;
}
```

いや、見返してみると意外と悪くないんじゃないか？

この時点で、BFSそのものとはあんまり関係ない&この下でも普通に使ってる変な文法みたいなのがいくつかあるのでメモる。

- bfs関数の引数に `vector` 等を取るところ。ここ普通に配列を渡したければたぶん`*`をつけることでポインタ渡しにすればOKだし今までそうしてきたんだけど、今回これだとバグる(エラー出る)。なんかバグる。何もつけないのも普通にダメだった。色々調べたらこれは`&`をつけて**参照渡し**にするのが正解手っぽい。だけどなんでかは現状まじでわからん。一旦深入りはやめて未来の自分にパス。
- `auto` というのは**型推論**というやつで、型名を明記せずに、コンパイラに決定を任せる書き方らしい。(実は出会うのは2度目)。文脈から型は絶対に定まるんだけど、長ったらしいとか書く価値がないという時に可読性を上げる等の目的で使えるっぽいです。正直今回のは`int`て書いて全く問題なかったと思うけど使ってみました。参考URL→[autoの使いどころ](https://uchan.hateblo.jp/entry/2019/02/22/105622)
- `for(auto next : G[start])` とかいうところ。これは**範囲for文**とか呼ぶっぽい。G[start]の中身全部をループで回す。正直詳しくないけど知ってれば雰囲気で読めるし、今夜は認識そのままで行きます。
- `assign`は、vectorをざあって初期化する関数。それだけ。

さて、くそ長い上に結局わからないことだらけな箇条書きを終えたところでBFSに焦点を当てる。まあでもわからないことを列挙しとくのは大いに意味があると信じてる。


##現状の浅めなBFSへの理解(メイン)
ひどいタイトルだけど少しはわかったつもりになったので。自分はBFSが怪しくなったらとりまここにだけ戻って来れば7割なんとかなる気がしてる。まあ無理になったら教科書まで立ち帰れば。

とりあえずBFSについて軽く読んで、それを受けて綺麗になったコードでもACしたので貼る。ご都合主義でbfs関数を一番下に書いて読みやすくしますた。

```abc151/d3.cpp
#include <bits/stdc++.h>
using namespace std;

using Graph = vector<vector<int>>;

void bfs(const Graph&, vector<int>&, queue<int>&);

int main() {
    int h,w;
    cin>>h>>w;
    vector<vector<char>> maze(h+2);
    int count = 0;

    //周りを壁で囲んでmaze作ってみた。あれ、悪くないのでは?
    for(int i=0; i<w+2; i++) maze[0].push_back('#');
    for(int i=1; i<=h; i++) {
        maze[i].push_back('#');
        for(int j=0; j<w; j++) {
            char s;
            cin>>s;
            if(s=='.') count++;
            maze[i].push_back(s);
        }
        maze[i].push_back('#');
    }
    for(int i=0; i<w+2; i++) maze[h+1].push_back('#');

    //グラフ入力作業
    Graph G(h*w+1);
    for(int i=1; i<=h; i++) {
        for(int j=1; j<=w; j++) {
            int posi = w*(i-1) + j;
            if(maze[i][j]=='.') {
                if(maze[i][j-1] == '.') G[posi].push_back(posi-1);
                if(maze[i-1][j] == '.') G[posi].push_back(posi-w);
                if(maze[i][j+1] == '.') G[posi].push_back(posi+1);
                if(maze[i+1][j] == '.') G[posi].push_back(posi+w);
            }
        }
    }


    vector<int> propo;
    for(int i=1; i<=h; i++) {
        for(int j=1; j<=w; j++) {
            if(maze[i][j]=='.') {
                vector<int> dist(h*w+1, -1);
                queue<int> todo;
                dist[w*(i-1)+j] = 0;
                todo.push(w*(i-1)+j);

                bfs(G, dist, todo);
                propo.push_back(*max_element(dist.begin(), dist.end()));
            }
        }
    }

    int ans = *max_element(propo.begin(), propo.end());
    cout<<ans<<endl;

    return 0;
}

//幅優先探索！
void bfs(const Graph& G, vector<int>& dist, queue<int>& todo) {
    while(!todo.empty()) {
        int v = todo.front();
        todo.pop();

        for(auto next_v : G[v]) {
            if(dist[next_v]!=-1) continue;

            dist[next_v] = dist[v] +1;
            todo.push(next_v);
        }
    }
}
```

ざっとBFSのアルゴリズムを日本語におこすと、

- グラフとしてデータを手に入れる。
- `queue` 型のtodoと、スタートからの距離を格納するvector(もしくは配列?)distを用意する。
- スタート地点を決めて、その頂点をtodoに入れる。
- todoが空になるまで繰り返し操作。todoの先頭を取り出し、そこと隣接する頂点を眺める。未訪問であれば、その頂点までの距離をdistに記録しつつ、todoリストにぶち込む。

て感じかな。これと上のコード見れば次回以降は自力で書けるはず。

初見コードとの違いは、訪問済みかどうかの判定とスタートからの距離を、両方まとめてdistで行えているところかな。一気に読みやすくなってる。頭いい。


##BFSの計算量
$N$、$M$をそれぞれ、BFSで探索する頂点・辺の数とする。ここ正直理解が曖昧なんだけど、

- 各頂点はキューに高々1回挿入され、高々1回取り出されるので、ここにかかる分が $O(N)$
- 各辺は高々1回だけ探索されるので、ここにかかる分が $O(M)$

というわけで合わせてBFS1回分の計算量は $O(N+M)$ らしいです。んーなんか騙されてる気がする。
ただまあとりあえず、グラフ入力を受け取るのと同じくらいの計算量で済むって理解しておけばいいかな。


##BFSの利点
グラフ探索をするとなったら、基本BFSでもDFSでも問題はない。が、それぞれ得意分野は存在する。DFSは今度お勉強したときに実感しながらまとめるとして、BFSは**最短経路を求めることができる**のが最大の特徴。たぶん。~~てかそれだけ説。~~まあいいや。

あと、道路に重みがある場合の最短経路は、**ダイクストラ法**とかいう高尚なアルゴリズムを使えば求められる。これはとても興味があるのでまた今度勉強しよう〜


##沼
これでひとまず問題は解けたんだけど、さっきのコードは各頂点(各マス)を1~h*wでナンバリングして扱っていた。今回はそんなにスケールが大きくなかったからよかったけど、このやり方だと一悶着ある瞬間がくるんじゃないかな？と思ったので。各マスを`pair`を用いて座標みたいに表して、それにBFSを適用してみた。らこの過程で色々苦戦した。のでその体験を適当にメモっていきます。

###ACコード
とりあえず貼ります。

```abc151/d4.cpp
#include <bits/stdc++.h>
using namespace std;

using P = pair<int, int>;  //firstがタテ、secondがヨコの座標
using Graph = map<P, vector<P>>;

//頂点(h,w)=(a,b)に、(i,j)が隣接しているとグラフに入力
void input(Graph& G, int a, int b, int i, int j) {
    P now,next;
    now.first = a;
    now.second = b;
    next.first = i;
    next.second = j;
    G[now].push_back(next);
}

void bfs(const Graph&, map<P, int>&, queue<P>&);

int main() {
    int h,w;
    cin>>h>>w;
    vector<vector<char>> maze(h+2);
    int count = 0;

    //周りを壁で囲んでmaze作ってみた。あれ、悪くないのでは?
    for(int i=0; i<w+2; i++) maze[0].push_back('#');
    for(int i=1; i<=h; i++) {
        maze[i].push_back('#');
        for(int j=0; j<w; j++) {
            char s;
            cin>>s;
            if(s=='.') count++;
            maze[i].push_back(s);
        }
        maze[i].push_back('#');
    }
    for(int i=0; i<w+2; i++) maze[h+1].push_back('#');

    //グラフ入力作業
    Graph G;
    for(int i=1; i<=h; i++) {
        for(int j=1; j<=w; j++) {
            if(maze[i][j]=='.') {
                if(maze[i][j-1] == '.') input(G,i,j,i,j-1);
                if(maze[i-1][j] == '.') input(G,i,j,i-1,j);
                if(maze[i][j+1] == '.') input(G,i,j,i,j+1);
                if(maze[i+1][j] == '.') input(G,i,j,i+1,j);
            }
        }
    }


    vector<int> propo;
    for(int i=1; i<=h; i++) {
        for(int j=1; j<=w; j++) {
            if(maze[i][j]=='.') {
                map<P, int> dist;
                queue<P> todo;
                P start;
                start.first = i;
                start.second = j;
                dist[start] = 1;
                todo.push(start);

                //bfs(G, dist, todo);
                while(!todo.empty()) {
                    P v = todo.front();
                    todo.pop();
                    for(P next_v : G[v]) {
                        if(dist[next_v]!=0) continue;

                        dist[next_v] = dist[v] +1;
                        todo.push(next_v);
                    }
                }

                int len = dist.size();
                int dist2[len];
                auto begin = dist.begin();
                auto end = dist.end();
                int k=0;
                for(auto iter=begin; iter!=end; iter++) {
                    dist2[k] = iter->second;
                    k++;
                }
                int max = *max_element(dist2, dist2+len);
                propo.push_back(max);
            }
        }
    }

    int ans = *max_element(propo.begin(), propo.end()) -1;
    cout<<ans<<endl;

    return 0;
}

    

//幅優先探索！
// void bfs(const Graph& G, map<P, int>& dist, queue<P>& todo) {
//     while(!todo.empty()) {
//         P v = todo.front();
//         todo.pop();
//         for(P next_v : G[v]) {
//             if(dist[next_v]!=0) continue;

//             dist[next_v] = dist[v] +1;
//             todo.push(next_v);
//         }
//     }
// }
```

- bfs関数を実装したらバグったのに、コードそのままにmain関数内に処理を入れたら普通に通った。なんで。エラーメッセージ見るとなんか`G[v]`とか書くとエラーになるっぽいんだけど本当にわかりません。値の受け渡しとかはたぶんできてるんだけどなあ。例の参照渡しとかの話か？
- `map`に格納された全ての要素をみる、みたいなことをしたい場面があった。コード終盤のようにイテレータを回すと、全要素に絡むことができる。
- きちんとは理解してないけど、mapって内部構造が二分木で、$O(logN)$ で各要素にアクセスできるみたいなデータ構造らしい。さらに、しれっと内部で要素がソートされているらしい。どっかでお勉強しようね。
- もしかしてmapって特殊なpairとして処理されてたりする...？　定義したmapがエラーコード内で`std::pair<const std::pair<int, int>, int>`みたいに表現されてた。知らんけど。

はい。他にも気になった件あったような気がするけど、昔のことなので忘れました。反省してます。