🐈

100日アルゴリズム[21日目・深さ優先探索]

2025/01/29に公開

 解いた問題https://leetcode.com/problems/maximum-number-of-fish-in-a-grid/description/

 解法hint1を見てDFSを使うことが書かれていたので、深さ優先探索で解きました。ヒントを見るまでその発想がなかったですが、adjacentという単語が出てきていたので、その単語からグラフ関係の解法が思いつけるかが肝です。
function findMaxFish(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

    const dfs = (r: number, c: number): number => {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] === 0) {
            return 0;
        }
        
        let fishCount = grid[r][c];
        grid[r][c] = 0; // 訪問済みとしてマーク

        for (const [dr, dc] of directions) {
            fishCount += dfs(r + dr, c + dc);
        }

        return fishCount;
    };

    let maxFish = 0;
    
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] > 0) {
                maxFish = Math.max(maxFish, dfs(r, c));
            }
        }
    }
    
    return maxFish;
}



 深さ優先探索上記の問題のhintに、深さ優先探索を使うことが書かれています。おおまかに説明すると、深さ優先探索は、木構造のグラフを深いところまで調べてみてそれ以上深い場所がなくなったら、一個戻ってもう一度深いところまで調べてみるというアルゴリズムです。
以下のようなコードになります。
TypeScriptで実装する場合は、Set型を使うとかなり便利です。また木構造なのでstartNodeの下にあるノードを探すforループがあります。以下のようなコードにすることで、ノードを調べていくことができます。
type Graph = {
    [key]:string: string[]
}

function depthFirstSearch(
_graph: Graph,
startNode:string,
_visited: Set<string>
):void {
    // 最初にstartNodeをvisitedのsetに加える
    _visited.add(startNode);

    for(const neighbor of _graph[startNode]) {
        if(!_visited.has(neighbor)) {
            depthFirstSearch(_graph,neighbor, _visited);
        }
    }
}

const graph = {
    A:["B","C"]
    B:["F","G"]
}

// Set型には重複のない要素が入る。
let visited: Set<string> = new Set();

function main (){
    depthFirstSearch(graph, "A", visited);
}

 参考https://qiita.com/drken/items/4a7869c5e304883f539b

解いた問題

解法

深さ優先探索

参考

Discussion