paizaラーニング レベルアップ問題集 幅優先探索・深さ優先探索メニュー JavaScript 領域の個数

領域の個数 (paizaランク A 相当)

JavaScriptで解いてみました。

解答コード例1 スタックで深さ優先探索

グリッドの一つのマスを、探索のスタート地点にします。
stackを用意して、深さ優先探索をします。
探索したところは探索済にします。
グリッド全てのマスについて、同様に探索します。

JavaScript

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//グリッドの行数 H , 列数 W
const [H, W] = lines[0].split(" ").map(Number);
//グリッド
const grid = lines.slice(1, H + 1).map(row => row.split(""));

let count = 0; //区画の数
//探索のスタート地点を決める
for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
        if (grid[i][j] !== ".") {
            continue;//探索できないなら次
        } else {
            count += 1;//探索できるならカウント
        }
        //スタックでの深さ優先探索     
        let stack = [[i, j]];//スタート地点のy, x座標
        //探索
        while (stack.length > 0) {
            const [y, x] = stack.pop();
            //探索できるところを訪問済にする
            //上
            if (y - 1 >= 0 && grid[y - 1][x] === ".") {
                grid[y - 1][x] = "#";//訪問済に
                stack.push([y - 1, x]);
            }
            //右
            if (x + 1 < W && grid[y][x + 1] === "."){
                grid[y][x + 1] = "#";
                stack.push([y, x + 1]);
            }
            //下
            if (y + 1 < H && grid[y + 1][x] === ".") {
                grid[y + 1][x] = "#";
                stack.push([y + 1, x]);
            }
            //左
            if (x - 1 >= 0 && grid[y][x - 1] === ".") {
                grid[y][x - 1] = "#";
                stack.push([y, x - 1]);
            }
        }
    }
}
console.log(count);

解答コード例2 関数で深さ優先探索1 (C++やJavaの場合の模範解答参考)

深さ優先探索の関数を定義します。
グリッドの１つのマスをスタート地点にして、深さ優先探索関数を実行します。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf8").trim();
const lines = input.split("\n");

const [H, W] = lines[0].split(" ").map(Number);

let grid = lines.slice(1).map(line => line.split(""));
//深さ優先探索関数定義
const dfs = (sy, sx) => {

        //移動は上,右,下,左の順
        if (sy - 1 >= 0 && grid[sy - 1][sx] === ".") {
            grid[sy - 1][sx] = "*";//訪問済み
            dfs(sy - 1, sx);
        }
         if (sx + 1 < W && grid[sy][sx + 1] === ".") {
            grid[sy][sx + 1] = "*";
            dfs(sy, sx + 1);
        }
        if (sy + 1 < H && grid[sy + 1][sx] === ".") {
            grid[sy + 1][sx] = "*";
            dfs(sy + 1, sx);
        }
        if (sx - 1 >= 0 && grid[sy][sx - 1] === ".") {
            grid[sy][sx - 1] = "*";
            dfs(sy, sx - 1);
        }
    
};

let ans = 0;//いくつの区画
//スタート地点を決める
for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
        if (grid[i][j] === ".") {
            ans += 1;
            grid[i][j] = "*";
            dfs(i, j);//探索実行
        }
    }
}
console.log(ans);

解答コード例3 関数で深さ優先探索2　(Python3の場合の模範解答参考)

深さ優先探索の関数を定義します。上下、左右でまとめます。
グリッドの１つのマスをスタート地点にして、深さ優先探索を実行します。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf8").trim();
const lines = input.split("\n");

const [H, W] = lines[0].split(" ").map(Number);

let grid = lines.slice(1).map(line => line.split(""));
//深さ優先探索関数定義
const dfs = (sy, sx) => {
    grid[sy][sx] = "#";//訪問済みに  
    for (let i = -1; i <= 1; i += 2) {
        //上下
        if (0 <= sy + i && sy + i < H && grid[sy + i][sx] === ".") {
            dfs(sy + i, sx);
        }
        //左右
        if (0 <= sx + i && sx + i < W && grid[sy][sx + i] === ".") {
            dfs(sy, sx + i);
        }
    }
};

let ans = 0;//いくつの区画
//スタート地点決める
for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
        if (grid[i][j] === ".") {
            dfs(i, j);//探索実行
            ans++;
        }
    }
}
console.log(ans);