概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
問題
m x nの2値行列の格子が与えられる。島は1（陸地）を4方向（水平または垂直）につなげたものである．
島は、島の中で値1を持つセルの数である。
グリッドの中の一番広い島の面積を返す。島がない場合は0を返す。
「200. Number of Islands」を拡張した問題ですので、まだ解いていない場合は以下のリンクから解いていくことをお勧めいたします。
C#で解くLeetCode「200. Number of Islands」
制約
m == grid.lengthn == grid[i].length1 <= m, n <= 50grid[i][j]は0もしくは1
解説
初めに、すべての位置に対して検索するようにfor文を二重に囲み、陸地だった場合島の範囲がどこまでかを確認します。
確認処理はDFS(深さ優先探索)で確認し、後程再帰的に実行するため関数化します。
MaxAreaOfIsland
public int MaxAreaOfIsland(int[][] grid)
{
int maxIslandSize = 0;
for (int i = 0; i < grid.Length; i++)
{
for (int j = 0; j < grid[0].Length; j++)
{
// 確認箇所が陸地だった場合
if (grid[i][j] == 1)
{
// DFS探索を行い陸地がどこまで続いているか確認
maxIslandSize = Math.Max(maxIslandSize, AreaOfIsland(grid, i, j));
}
}
}
return maxIslandSize;
}DFSでの陸地確認処理では「最初に渡された値が異常値だった場合」または、「陸地ではなかった場合」は何もせずに終了とします。
そして陸地だった場合は重複して確認しないよう使用しない他の数字で上書きします。
四方を再度確認し、再帰的な処理が終了すれば島の範囲がすべて探索済みになります。
現在地を含め、探索処理で見つけた島の広さを返して終了です。
注意点として、このメソッドは再帰的な処理でマイナスになる可能性がありますので異常確認を忘れずに書きましょう。
AreaOfIsland
private int AreaOfIsland(int[][] grid, int i, int j)
{
// 探索対象が異常値だった場合探索しない
if (i < 0 || j < 0)
{
return 0;
}
// 探索対象が異常値だった場合探索しない
if (i >= grid.Length || j >= grid[0].Length)
{
return 0;
}
// 陸地ではなかった場合探索しない
if (grid[i][j] != 1)
{
return 0;
}
// 探索済み箇所にする
grid[i][j] = 2;
// 島の広さを数える
var areaCount = 1;
areaCount += AreaOfIsland(grid, i + 1, j);
areaCount += AreaOfIsland(grid, i - 1, j);
areaCount += AreaOfIsland(grid, i, j + 1);
areaCount += AreaOfIsland(grid, i, j - 1);
return areaCount;
}
ソースコード
Solution.cs
public class Solution {
public int MaxAreaOfIsland(int[][] grid)
{
int maxIslandSize = 0;
for (int i = 0; i < grid.Length; i++)
{
for (int j = 0; j < grid[0].Length; j++)
{
// 確認箇所が陸地だった場合
if (grid[i][j] == 1)
{
// DFS探索を行い陸地がどこまで続いているか確認
maxIslandSize = Math.Max(maxIslandSize, AreaOfIsland(grid, i, j));
}
}
}
return maxIslandSize;
}
private int AreaOfIsland(int[][] grid, int i, int j)
{
// 探索対象が異常値だった場合探索しない
if (i < 0 || j < 0)
{
return 0;
}
// 探索対象が異常値だった場合探索しない
if (i >= grid.Length || j >= grid[0].Length)
{
return 0;
}
// 陸地ではなかった場合探索しない
if (grid[i][j] != 1)
{
return 0;
}
// 探索済み箇所にする
grid[i][j] = 2;
var areaCount = 1;
// 隣接地が陸地かどうか確認するために再帰的に処理を実行する
areaCount += AreaOfIsland(grid, i + 1, j);
areaCount += AreaOfIsland(grid, i - 1, j);
areaCount += AreaOfIsland(grid, i, j + 1);
areaCount += AreaOfIsland(grid, i, j - 1);
return areaCount;
}
}