【就プロ】幅優先探索

はじめに

先日投稿しました以下の記事で深さ優先探索を紹介させていただきました。
takahiro-itazuri.hatenadiary.jp

今回は深さ優先探索と双璧をなす幅優先探索を紹介します。
深さ優先探索を理解している人にとっては非常にわかりやすいと思いますので、是非セットで覚えてください。

幅優先探索（breadth-first search, BFS）は簡単に述べると「同じ幅（深さ）のものを網羅的に探索していく方法」です。

以下の画像はWikipediaより添付させていただきました画像です。

上の画像のように同じ深さから順番に探索していくアルゴリズムです。

グラフ構造の探索においては
時間計算量は$O(\|E\|)$
空間計算量は$O(\|V\|)$
となります。

問題設定

問題文

$N \times N$の碁盤目状の道がある時、$(x,y)=(1,1)$から$(x,y)=(N,N)$に行くための最短経路の数を数えろ。

入力

碁盤の目の数$N$

N

出力

最短経路の総数

アルゴリズムと実装

キュー

考えるべきことは以下の通りです。

• 待ち行列を保存するキュー
• 探索を行うためのアルゴリズム

アルゴリズムは以下のようになります。

1. キューを初期化
2. キューの先頭から一つ要素を取り出す
3. 取り出した要素から探索を行い、新しい要素をキューの後ろに追加
4. キューの中身がなくなるまで2~3を繰り返す

C++

#include<iostream>
#include<queue>

int N;
int count = 0;

struct pos {
    int x;
    int y;
};

class Queue {
public:
    Queue();
    ~Queue();
    void offer(pos p);
    pos poll();
    void search(pos p);
    void show();
    bool isEmpty();
private:
    std::queue<pos> queue;
};

Queue::Queue() {
    offer({ 1, 1 });
}

Queue::~Queue() {}

void Queue::offer(pos p) {
    queue.push(p);
}

pos Queue::poll() {
    pos p = queue.front();
    queue.pop();

    if (p.x == N && p.y == N) count++;

    return p;
}

void Queue::search(pos p) {
    if (p.y < N) offer({ p.x, p.y + 1 });
    if (p.x < N) offer({ p.x + 1, p.y });
    return;
}

void Queue::show() {
    std::queue<pos> buf(queue);

    std::cout << "{" << std::endl;
    while (!buf.empty()) {
	pos p = buf.front();
	std::cout << "    [" << p.x << ", " << p.y << "]" << std::endl;
	buf.pop();
    }
    std::cout << "}" << std::endl;
}

bool Queue::isEmpty() {
    if (queue.empty()) return true;
    else return false;
}

int main(int argc, char* argv[]) {
    std::cout << ">> ";
    std::cin >> N;

    Queue q;

    while (!q.isEmpty()) {
        pos p = q.poll();
	q.search(p);
    }

    std::cout << count << std::endl;
    system("pause");
    return 0;
}

実行結果

>> 3
6