C#で解くLeetCode「200. Number of Islands」

概要

エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。

問題

200. Number of Islands

1（陸）と0（水）の地図を表すm×nのchar型の2次元配列が与えられたとき、島の数を返す。

島は水に囲まれ、隣接する陸地が水平または垂直に結ばれて形成される。グリッドの4つの辺はすべて水に囲まれていると考えてよい。

制約

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j]は'0'もしくは'1'

解説

初めに、すべての位置に対して検索するようにfor文を二重に囲み、陸地だった場合島の範囲がどこまでかを確認します。
確認処理はDFS(深さ優先探索)で確認し、後程再帰的に実行するため関数化します。

NumIslands

public int NumIslands(char[][] grid)
{
    var count = 0;

    for (int i = 0; i < grid.Length; i++)
    {
        for (int j = 0; j < grid[0].Length; j++)
        {
            // 確認箇所が陸地だった場合
            if (grid[i][j] == '1')
            {
                // DFS探索を行い陸地がどこまで続いているか確認
                DFSMarking(grid, i, j);
                count++;
            }
        }
    }
    return count;
}

DFSでの陸地確認処理では「最初に渡された値が異常値だった場合」または、「陸地ではなかった場合」は何もせずに終了とします。
そして陸地だった場合は重複して確認しないよう使用しない他の文字で上書きします。
最後に四方を再度確認し、再帰的な処理が終了すれば、島の範囲がすべて探索済みになります。
注意点として、このメソッドは再帰的な処理でマイナスになる可能性がありますので異常確認を忘れずに書きましょう。

SubarraySum

private void DFSMarking(char[][] grid, int i, int j)
{
    // 探索対象が異常値だった場合探索しない
    if (i < 0 || j < 0)
    {
        return;
    }

    // 探索対象が異常値だった場合探索しない
    if (i >= grid.Length || j >= grid[0].Length)
    {
        return;
    }

    // 陸地ではなかった場合探索しない
    if (grid[i][j] != '1')
    {
        return;
    }

    // 探索済み箇所にする
    grid[i][j] = '#';


    // 隣接地が陸地かどうか確認するために再帰的に処理を実行する
    DFSMarking(grid, i + 1, j);
    DFSMarking(grid, i - 1, j);
    DFSMarking(grid, i, j + 1);
    DFSMarking(grid, i, j - 1);
}

ソースコード

Solution.cs

public class Solution {
    public int NumIslands(char[][] grid)
    {
        if (grid == null)
        {
            return 0;
        }

        var count = 0;

        for (int i = 0; i < grid.Length; i++)
        {
            for (int j = 0; j < grid[0].Length; j++)
            {
                if (grid[i][j] == '1')
                {
                    // DFS探索を行い、発見した島を検索対象から除外する
                    DFSMarking(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    
    private void DFSMarking(char[][] grid, int i, int j)
    {
        // 探索対象が異常値だった場合探索しない
        if (i < 0 || j < 0)
        {
            return;
        }

        // 探索対象が異常値だった場合探索しない
        if (i >= grid.Length || j >= grid[0].Length)
        {
            return;
        }

        // 島ではなかった場合探索しない
        if (grid[i][j] != '1')
        {
            return;
        }

        // 探索済みにする
        grid[i][j] = '#';

        // 隣接地が陸地かどうか確認するために再帰的に処理を実行する
        DFSMarking(grid, i + 1, j);
        DFSMarking(grid, i - 1, j);
        DFSMarking(grid, i, j + 1);
        DFSMarking(grid, i, j - 1);
    }
}

概要

問題

制約

解説

ソースコード

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル