JavaScriptで幅優先探索 (bfs) を実装する

JavaScriptで幅優先探索 (bfs) を実装する

2020-01-139 min read

目次

  1. 概要
  2. bfsソースコード

概要

JavaScriptで幅優先探索 (bfs) を実装し簡単な最短経路の探索問題を解いてみました。

AtCoderの問題を参考にしています

https://atcoder.jp/contests/abc007/tasks/abc007_3

bfsソースコード

前提

bfs 関数の定義について

引数 tableは、れぞれのマスが通行可能な空きマス(.)か通行不可能な壁マス(#) で定義されている2次元配列です。

引数 start は、探索のスタート一であり [y, x] の形式の配列で渡します。

引数 goal は、探索のスタート一であり [y, x] の形式の配列で渡します。

それぞれの引数の詳細はテストコードをご覧ください。

bfs関数

function bfs(table, start, goal) {
    const d = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    const queue = [];
    const H = table.length
    const W = table[0].length
    const min = [...Array(H)].map(n => [...Array(W)].fill("*"));
    queue.push(start);
    min[start[0]][start[1]] = 0;
    // Queue に残りがある限りループする
    while (queue.length > 0) {
        const p = queue.shift();
        // ゴールに到着しているならbreak
        if (p[0] === goal[0] && p[1] === goal[1]) {
            break;
        }
        // 右、下、左、上の順でチェック
        for (let i = 0; i < d.length; i++) {
            const next_y = p[0] + d[i][0];
            const next_x = p[1] + d[i][1];
            // はみ出し、壁衝突を考慮する
            if (next_y < 0 || W <= next_x) continue;
            if (next_x < 0 || H <= next_y) continue;
            if (table[next_y][next_x] === '#') continue;
            if (min[next_y][next_x] !== '*') continue;
            // 新しいポジションへの移動は現地点への最短経路+1となる
            queue.push([next_y, next_x]);
            min[next_y][next_x] = min[p[0]][p[1]] + 1;
        }
    }
    return min[goal[0]][goal[1]];
}

テストコード

"use strict";
main()
function main() {
    const S = [1, 1] // start
    const G = [1, 3] // goal
    const T = [
        "########",
        "#.#....#",
        "#.###..#",
        "#......#",
        "########",
    ].map(n => n.split(""));
    const answer = bfs(T, S, G)
    console.log(answer) // 10
}
Recommends
JavaScriptで幅優先探索 (bfs) を実装する
2020-01-13
javascript
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
JavaScriptの配列ショートハンド (AtCoder用)
2020-07-05
javascript
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
JavaScript で bit全探索
2019-06-10
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
atcoder
深さ優先探索アルゴリズムを実装 部分和問題を解く
2018-12-25
javascript
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
javascriptで累積和を解く
2022-02-27
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0%E3%83%9F%E3%83%B3%E3%82%B0
atcoder
JavaScriptで優先度付きキューを実装する
2021-08-01
javascript
typescript
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
next_permutationをJSで実装する
2021-07-22
javascript
typescript
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
10進数から2進数 2進数から10進数への変換 JavaScript
2020-07-12
javascript
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
JavaScriptでワーシャルフロイド法を実装
2020-06-21
javascript
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
JavaScriptによる2分探索(バイナリサーチ) のサンプルコード
2020-05-24
javascript
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
順列・組み合わせ のサンプルコード JS [permutation] [combina...
2019-06-30
javascript
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
ブラウザで動くAtCoder用のデバッガを作ってみた (JSのみ)
2019-05-02
javascript
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
atcoder
素因数分解を行うプログラム サンプルコード JS/PHP
2018-12-24
javascript
php
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
複数キーでソートするサンプルコード JavaScript
2018-11-05
javascript
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
【JavaScript】AtCoderとかでも利用したい、ブラウザで動くエディタ + デバ...
2018-08-29
javascript
semantic%20ui
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
New Posts
[CDK]SNS+SQS+DynamoDBでBounceとComplaint情報を収集する...
2022-04-11
amazon%20aws
node.js
typescript
[AmazonSES] node.js と ejs を利用してEメールを送信する
2022-04-09
javascript
node.js
amazon%20aws
GatsbyからNext.jsへのサイト移行
2022-04-04
next.js
gatsby
amazon%20aws
[AWS CDK] Lambda で S3 オブジェクトを読み書きするStackの構築
2022-03-18
aws%20cdk
amazon%20aws
typescript
[AWS CDK] S3 + CloudFrontの構築とOriginAccessIden...
2022-03-09
amazon%20aws
aws%20cdk
typescript
[AWS CDK] Bastion(踏み台)構築。SSMとEC2InstanceConne...
2022-03-06
amazon%20aws
aws%20cdk
node.js
[AWS CDK] Cognito を構築
2022-03-04
amazon%20aws
aws%20cdk
node.js
AWS CDK v2 でVPC上にAPI Gateway + Lambda + RDS +...
2022-02-28
amazon%20aws
aws%20cdk
node.js
javascriptで累積和を解く
2022-02-27
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0%E3%83%9F%E3%83%B3%E3%82%B0
atcoder
AWS Amplify で monorepo を導入し 単一リポジトリで複数プロジェクトを...
2022-02-25
git
github
amazon%20aws
AWS CDK v2 で Lambda関数のデプロイ
2022-02-23
typescript
amazon%20aws
aws%20cdk
NextJSでDevToysのようなものを作成した
2022-02-22
javascript
typescript
vercel
JSで動的計画法を利用して部分和問題を解く
2022-02-20
javascript
typescript
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
NestJSアプリケーションをwebpackでBundle
2022-02-20
javascript
typescript
nestjs
[Next.js] Warning: Assign arrow function to a...
2022-02-13
javascript
typescript
next.js
Hot posts!
Proxy環境下でcurlを実行する
2019-12-07
linux
curl
OpenCVのMatのタイプ一覧表
2018-11-25
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86
opencv
Macでも利用できるDBクライアント MySQL PostgreSQL Oracle など
2019-12-21
linux
%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9
mysql
TablePlusを使ってみる。シンプルでモダンなSQLクライアントツール
2018-09-30
%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9
DBクライアントツールはDBeaverをおすすめしたい
2021-03-08
oracle
mysql
sqlite
AWS S3のアクセスキーIDとシークレットアクセスキーの取得 作業用ユーザを作成
2019-06-12
amazon%20aws
linux
amazon%20s3
AtCoderで初めて色がつくまでの話(茶色) レートが中々上がらなかった原因
2018-11-25
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
%E9%9B%91%E8%AB%87
CentOS8でEPELとPowerToolsリポジトリの有効化
2020-11-30
centos
red%20hat
EPEL
Macでターミナルからポートスキャンを行う方法。
2018-12-09
linux
mac
apple
Python + OpenCVのfillConvexPolyで複雑なポリゴンを描画する
2018-11-27
python
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86
opencv
Date
▶︎
2022 年 (21)
▶︎
2021 年 (40)
▶︎
2020 年 (30)
▶︎
2019 年 (90)
▶︎
2018 年 (89)
▶︎
2017 年 (1)
Tags
javascript(92)
linux(47)
amazon%20aws(39)
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0(36)
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86(30)
node.js(30)
html5(29)
centos(24)
php(23)
python(22)
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0(20)
typescript(20)
canvas(18)
mac(18)
opencv(17)
mysql(17)
%E9%9B%91%E8%AB%87(15)
wordpress(15)
docker(14)
atcoder(13)
apache(12)
%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92(12)
%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9(12)
red%20hat(12)
ubuntu(11)
amazon%20s3(11)
github(10)
git(10)
vue.js(10)
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86100%E6%9C%AC%E3%83%8E%E3%83%83%E3%82%AF(10)
css3(8)
%E5%8F%AF%E8%A6%96%E5%8C%96(8)
%E5%B0%8F%E3%83%8D%E3%82%BF(8)
mariadb(8)
amazon%20lightsail(7)
react(7)
%E3%83%96%E3%83%AD%E3%82%B0(6)
cms(6)
oracle(6)
perl(6)
gitlab(6)
next.js(6)
aws%20cdk(6)
iam(5)
amazon%20ec2(5)
aws%20amplify(5)
curl(4)
webassembly(4)
ssh(4)
homebrew(4)
Author
s-yoshiki
s-yoshiki
githubzenntwitterqiita
ただの備忘録です。
JavaScript/TypeScript/node.js/React/AWS/OpenCV
※このブログの内容は個人の見解であり、所属する組織等の見解ではありません。