1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

Day 17

JavaScript Advent Calendar 2025

@Haru_K0720(Haru_K)

💡幅優先探索（BFS） (paiza:陣取りの結末)

1
Last updated at Posted at 2025-12-12

今回は paiza の「陣取りの結末」の問題に挑戦！

新たに BFS のアルゴリズムについて学んだ！


🧩 問題概要

🎮 問題の設定

  • 盤面は H×W。
  • マスには以下の 3 種類がある：
    • '*' … プレイヤーの現在の陣地（スタート地点は必ず 1 つ）
    • '.' … 何もないマス（進める）
    • '#' … 障害物（進めない）

🎯 プレイヤーの操作

  • プレイヤーの陣地（'*'）から 上下左右に 1 マス移動できる。
  • 移動できる '.' マスはすべて '*' に塗り替える。
  • 新しく '*' になったマスからもさらに広がっていく。
  • '#' は通れない & 塗れない。
  • もう広がらなくなるまで続ける。

📝 最終的に…

  • 陣地として到達できたマスすべてが '*' になった盤面を出力する。



入力例：

3 3
*.#
..#
##.

出力例：

**#
**#
##.






🔺OK？例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];

rl.on('line', (input) => lines.push(input));

rl.on('close', () => {
    const [H, W] = lines[0].split(' ').map(Number);
    const gridS = lines.slice(1).map(line => line.split(''));
    
    while (true){
        let change = false;
        
        for (let i = 0; i < H; i++) {
            for (let j = 0; j < W; j++) {
                if (gridS[i][j] === '*') {
                    if (i > 0 && gridS[i-1][j] === '.') {
                        gridS[i-1][j] = '*'; 
                        change = true;
                    }
                    if (i < H-1 && gridS[i+1][j] === '.') {
                        gridS[i+1][j] = '*'; 
                        change = true;
                    }
                    if (j > 0 && gridS[i][j-1] === '.') {
                        gridS[i][j-1] = '*'; 
                        change = true;
                    }
                    if (j < W-1 && gridS[i][j+1] === '.') {
                        gridS[i][j+1] = '*'; 
                        change = true;
                    }
                }
                
            }
        }
        
        if (!change) {
            gridS.forEach(s => console.log(s.join('')));
            return;
        }
    }
});

  • * は、障害物 # を避けつつ上下左右の . に広がる
  • 広がらなくなるまで繰り返す
  • 最終形を出力する

テストケースは一応通過したが、アルゴリズムとしては非効率かつTLEしやすくて危険なので、あまり良くなさそう。






✅ OK例：幅優先探索（BFS）

const rl = require('readline').createInterface({ input: process.stdin });
const lines = [];

rl.on('line', (line) => lines.push(line));
rl.on('close', () => {
    const [H, W] = lines[0].split(' ').map(Number);
    const s = lines.slice(1).map(line => line.split(''));

    // BFS キュー
    const my_p = [];

    // 最初の * の位置をすべてキューへ
    for (let y = 0; y < H; y++) {
        for (let x = 0; x < W; x++) {
            if (s[y][x] === '*') {
                my_p.push([y, x]);
            }
        }
    }

    // BFS
    while (my_p.length > 0) {
        const [y, x] = my_p.shift(); // pop(0)

        if (y > 0 && s[y - 1][x] === '.') {
            s[y - 1][x] = '*';
            my_p.push([y - 1, x]);
        }
        if (y < H - 1 && s[y + 1][x] === '.') {
            s[y + 1][x] = '*';
            my_p.push([y + 1, x]);
        }
        if (x > 0 && s[y][x - 1] === '.') {
            s[y][x - 1] = '*';
            my_p.push([y, x - 1]);
        }
        if (x < W - 1 && s[y][x + 1] === '.') {
            s[y][x + 1] = '*';
            my_p.push([y, x + 1]);
        }
    }

    // 出力
    for (let y = 0; y < H; y++) {
        console.log(s[y].join(''));
    }
});

🎯 まず BFS（幅優先探索）とは何か？

📢 一言で言うと……
近い場所から順番に探索を広げていく方法。

水がじわ〜っと四方向に広がっていくイメージ。


🌊 BFS の具体例

* がスタートだとすると BFS はこう広がる。

  • * がある地点をキューに入れる（スタート）
  • キューから取り出す
  • 上下左右を調べる
  • 到達できる場所（'.'）を新たな * にし、キューに追加する
  • キューが空になるまで繰り返す

これを続けると、最終的には上下左右に行けるだけ * が広がる。


🗒️ BFSの特徴

✔ 近い順に広がる
キュー（FIFO）を使うことで、「先に入れた場所から順に処理」される。

✔ 無駄な重複探索をしない
一度訪れたところはまたキューに入れない → 効率が良い。

✔ 最短距離探索にも使える
迷路で最短手を求めるとき BFS が使われるのはこのため。



🔍 では、この問題で BFS がどう使われているか？

問題文の要点：

  • * はプレイヤーの陣地
  • 上下左右に進める限り、すべて陣地（*）に塗り替える
  • # は障害物なので通れない

つまり、

「プレイヤーの陣地から上下左右に行ける場所をすべて塗りつぶす」
→ これはまさに BFS




💻 ここからコードの解説

① 入力の読み込み

const [H, W] = lines[0].split(' ').map(Number);
const s = lines.slice(1).map(line => line.split(''));
  • H 行、W 列の盤面を 2 次元配列 s に格納。



② 最初にある * をすべて探してキューに追加

const my_p = [];

for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++) {
        if (s[y][x] === '*') {
            my_p.push([y, x]);
        }
    }
}

複数の * があっても OK。
BFS は複数起点でも問題なく同時に広がる。



③ BFS 開始（キューが空になるまで）

while (my_p.length > 0) {
    const [y, x] = my_p.shift();  // 先頭を取り出す

ここで BFS の本体。

※ shift() は Array インスタンスのメソッドで、配列から最初の要素を取り除き、その要素を返す。このメソッドは配列の長さを変える。


周囲4方向を確認する

if (y > 0 && s[y - 1][x] === '.') {
    s[y - 1][x] = '*';
    my_p.push([y - 1, x]);
}
  • '.' なら進める → * に塗る
  • 新しい陣地も BFS の次の探索対象（だからキューへ push）

下・左・右も同様。



④ BFS 完了後に盤面出力

for (let y = 0; y < H; y++) {
    console.log(s[y].join(''));
}






🗒️ まとめ

🔹 1. この問題は「到達可能なマスを全部塗る」問題

障害物 '#' を除いて
スタート地点 '*' から つながっているすべてのマスを塗りつぶす だけの問題。

→ 広がり方は「上下左右のみ」。


🔹 2. 最適解は BFS（幅優先探索）

理由：

  • 陣地が 起点から四方に広がる動作 → まさに BFS 。
  • 一度訪れたマスをもう一度見ない → 効率がいい。
  • 最大でも 20×20 = 400 マス → BFS なら十分高速。

🔹 3. BFS の基本動作

  • キュー（FIFO）にスタートを入れる
  • キューから取り出す
  • 上下左右を調べる
  • 行ける場所なら塗って、次の探索対象としてキューへ追加
  • キューが空になるまで繰り返す

→ これで全ての到達可能地点を確実に探索できる。


🔹 4. なぜ while(true) 全探索ループ法は非推奨か

最初に書いた方法：

  • 全マスを毎回チェック
  • 塗り替えが起きるたびに再スキャン
  • 最大 400 マス × 400 回 = 160,000 回
    → 小さな問題なら動くが、一般的な問題では 「TLE」の原因になる

BFS は「必要なところだけ順に処理」できるので格段に効率が良い。


🔹 5. BFS 実装のポイント（JS版）

  • queue.shift() で先頭を取り出す（FIFO）
  • 塗ったら push() して次の探索点に追加
  • 陣地にできたら '*' に書き換えるので「調査済みフラグ」になる（重複防止）
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?