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%B0atcoderbfs
    

目次

概要

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
}
    
s-yoshiki
s-yoshiki
githubtwitterqiita
Web作ってますが、インタラクティブなプログラミングも好きです。
JavaScript / Vue / node.js / PHP / AWS / OpenCV

関連記事

JSで32ビット符号付き整数に対してのビット演算でハマった
具体例 参考にしたサイト JSでサブネットマスクの計算を行おうとしたとき、ビット演算でハマりました。その時のメモです。 JSでサブネットマスクの計算 JSでビット演算子を利用する場合 3…

JSでIPアドレスがサブネットマスクで指定した範囲内にあるか判定する
IPアドレスが指定した範囲内にあるかどうか判定 参考にしたサイト JSでIPアドレス(IPv4)が指定したサブネットの範囲に含まれるか判定するロジックを作った時の記録です。 IPアドレスが指定した範囲内にあるかどうか判定 処理としては、IP…

プログラムの数値計算で発生する誤差の種類 丸め誤差・打ち切り誤差・桁落ち
はじめに 誤差の種類 丸め誤差 打ち切り誤差 桁落ち 情報落ち 桁溢れ誤差 参考にしたサイト コンピュータで出てくる誤差はいくつかありますが、 それらをコードに落として整理しました。 はじめに 例えば の計算の答えは 0.6666666666…

JSでサブネットマスクの計算
JSによるサブネットマスク関連の計算 IPv4アドレス文字列をNumber型に変換する CIDR と サブネットの相互変換 ネットワークアドレス と ブロードキャストアドレス クラス 改めて計算方法を整理する 参考にさせていただいたサイト JSでIPv…

AWS Amplify に Next.js (SSG) で作ったアプリをデプロイする
はじめに 操作 Next.js (React) アプリの作成、Gitへのプッシュ AWS Amplifyでプロジェクト作成 参考にしたサイト この記事では、React / Next.js アプリケーションを作成し、AWS Amplify…

Typescriptに入門した
初期作業 とりあえずHello World 初期作業 typescript環境を作っていきます。 とりあえずHello World まず、次のサンプルコードを作成します。 typescriptファイルをビルドします。

Vue/Nuxt.js 触ってた人が Next.js に入門する
はじめに 実施環境 学習ガイド Create a Next.js App Navigate Between Pages ページの作成 リンク Assets, Metadata, and CSS Assets メタデータ CSS…

10進数から2進数 2進数から10進数への変換 JavaScript
10進数から2進数 2進数から10進数 テスト 10進数から2進数、2進数から10進数への変換を行うJavaScriptのコードの紹介。 JSの場合、10進数から2進数への変換はメソッド。2進数から1…

JavaScriptの配列ショートハンド (AtCoder用)

JavaScriptでワーシャルフロイド法を実装
AtCoder ABC012 D問題 D - バスと避けられない運命 解説 実装 AtCoder ABC012 の D問題でワーシャルフロイド法が利用できる問題が出てきたので、 JavaScriptで実装しました。 AtCoder ABC012 D問題 D…

最新の投稿

Python poetryでパッケージ開発 PyPIで公開 Pytestでテスト CIをGitHub Actionsで回す
Poetry でパッケージ開発 pytest でユニットテストを実施しカバレッジを算出する パッケージをビルドし PyPI で公開する 検証環境にデプロイする 本番環境にデプロイする GitHub Actions で CI を回す codecovの設定 GitHub…

Perlでconstant(定数)をhashのキーに使う
ハマった事象 解決方法 1 括弧をつける 2 & をつける 参考にしたサイト Perlでconstant(定数)をhash…

php-fpmのステータスページを表示 Apache & htaccess
試した環境 php-fpm の pm.status_path について php-fpmのconfの設定 .htaccess の設定 アクセスしてみる 参考にしたサイト Apache環境で php-fpm のステータスページを htaccess…

DBクライアントツールはDBeaverをおすすめしたい
DBeaver について 特徴 対応DB 対応OS 利用環境 アーカイブ インストール windows mac Linux コネクションの作成 SQLを実行する その他 CloudBeaverについて 今までいくつかのDB…

CentOS8 に Oracle12.2 clientをインストールする
実施した環境 セットアップ clientツールの 準備 インストール 環境変数にパスを通す 実行 libnsl.so.1: cannot open shared object file と表示される場合 CentOS8 に Oracle12.2 client…

フェールセーフやフェールソフト・フールプルーフ 障害対策用語の整理

JSで32ビット符号付き整数に対してのビット演算でハマった
具体例 参考にしたサイト JSでサブネットマスクの計算を行おうとしたとき、ビット演算でハマりました。その時のメモです。 JSでサブネットマスクの計算 JSでビット演算子を利用する場合 3…

Gitにプロキシを設定する
プロキシを設定する 確認 Gitでプロキシを通しておくメモです。 プロキシを設定する 以下のコマンドでproxyを通します。 ※ がプロキシのURL…

JSでIPアドレスがサブネットマスクで指定した範囲内にあるか判定する
IPアドレスが指定した範囲内にあるかどうか判定 参考にしたサイト JSでIPアドレス(IPv4)が指定したサブネットの範囲に含まれるか判定するロジックを作った時の記録です。 IPアドレスが指定した範囲内にあるかどうか判定 処理としては、IP…

プログラムの数値計算で発生する誤差の種類 丸め誤差・打ち切り誤差・桁落ち
はじめに 誤差の種類 丸め誤差 打ち切り誤差 桁落ち 情報落ち 桁溢れ誤差 参考にしたサイト コンピュータで出てくる誤差はいくつかありますが、 それらをコードに落として整理しました。 はじめに 例えば の計算の答えは 0.6666666666…

Tags

Dates

© 2021   404 motivation not found