
JavaScriptで幅優先探索 (bfs) を実装する
2020-01-139 min read
目次
概要
JavaScriptで幅優先探索 (bfs) を実装し簡単な最短経路の探索問題を解いてみました。
AtCoderの問題を参考にしています
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の配列ショートハンド (AtCoder用)
2020-07-05
JavaScript で bit全探索
2019-06-10
深さ優先探索アルゴリズムを実装 部分和問題を解く
2018-12-25
javascriptで累積和を解く
2022-02-27
JavaScriptで優先度付きキューを実装する
2021-08-01
next_permutationをJSで実装する
2021-07-22
10進数から2進数 2進数から10進数への変換 JavaScript
2020-07-12
JavaScriptでワーシャルフロイド法を実装
2020-06-21
JavaScriptによる2分探索(バイナリサーチ) のサンプルコード
2020-05-24
順列・組み合わせ のサンプルコード JS [permutation] [combina...
2019-06-30
ブラウザで動くAtCoder用のデバッガを作ってみた (JSのみ)
2019-05-02
素因数分解を行うプログラム サンプルコード JS/PHP
2018-12-24
複数キーでソートするサンプルコード JavaScript
2018-11-05
【JavaScript】AtCoderとかでも利用したい、ブラウザで動くエディタ + デバ...
2018-08-29
New Posts
[CDK]SNS+SQS+DynamoDBでBounceとComplaint情報を収集する...
2022-04-11
[AmazonSES] node.js と ejs を利用してEメールを送信する
2022-04-09
GatsbyからNext.jsへのサイト移行
2022-04-04
[AWS CDK] Lambda で S3 オブジェクトを読み書きするStackの構築
2022-03-18
[AWS CDK] S3 + CloudFrontの構築とOriginAccessIden...
2022-03-09
[AWS CDK] Bastion(踏み台)構築。SSMとEC2InstanceConne...
2022-03-06
[AWS CDK] Cognito を構築
2022-03-04
AWS CDK v2 でVPC上にAPI Gateway + Lambda + RDS +...
2022-02-28
javascriptで累積和を解く
2022-02-27
AWS Amplify で monorepo を導入し 単一リポジトリで複数プロジェクトを...
2022-02-25
AWS CDK v2 で Lambda関数のデプロイ
2022-02-23
NextJSでDevToysのようなものを作成した
2022-02-22
JSで動的計画法を利用して部分和問題を解く
2022-02-20
NestJSアプリケーションをwebpackでBundle
2022-02-20
[Next.js] Warning: Assign arrow function to a...
2022-02-13
Hot posts!
Proxy環境下でcurlを実行する
2019-12-07
OpenCVのMatのタイプ一覧表
2018-11-25
Macでも利用できるDBクライアント MySQL PostgreSQL Oracle など
2019-12-21
TablePlusを使ってみる。シンプルでモダンなSQLクライアントツール
2018-09-30
DBクライアントツールはDBeaverをおすすめしたい
2021-03-08
AWS S3のアクセスキーIDとシークレットアクセスキーの取得 作業用ユーザを作成
2019-06-12
AtCoderで初めて色がつくまでの話(茶色) レートが中々上がらなかった原因
2018-11-25
CentOS8でEPELとPowerToolsリポジトリの有効化
2020-11-30
Macでターミナルからポートスキャンを行う方法。
2018-12-09
Python + OpenCVのfillConvexPolyで複雑なポリゴンを描画する
2018-11-27
Date
▶︎
2022 年 (21)
▶︎
2021 年 (40)
▶︎
2020 年 (30)
▶︎
2019 年 (90)
▶︎
2018 年 (89)
▶︎
2017 年 (1)
Tags
Author