LeetCode 1000000本ノック【200. Number of Islands】

# 目次

|No.|項目|
|:----:|:-------------|
| 1 | [概要](#概要) |
| 2 | [問題](#問題) |
| 3 | [解法](#解法) |
| 4 | [メイキング](#メイキング) |

# 概要
<!-- 発端や概要を記載 -->
●発端
　・競プロ初心者、コーディング面接でズタボロにされ、
　・最低限のアルゴリズム学習とコーディング力強化を習慣化するため記事化
●環境
　・LeetCodeブラウザ上で実装（vscodeに拡張機能にするかもシレナイ）
　・言語はpython3
●その他ルール
　・google検索は自由に（直接的なLeetCodeの問題解説ページはNG）
　　（60分実装して実装出来なければ解説ページ参照）
　・[コーディング面接対策のために解きたいLeetCode 60問](https://1kohei1.com/leetcode/)から問題選出
　・「1000000」は任意の2進数とする


<!-- 各チャプター -->
# 問題
- [200. Number of Islands](https://leetcode.com/problems/number-of-islands/)


>Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

>An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

⇨「0を海、1を陸に見立てたグリッド図で、島は何個あるのか？
　ちなみに島ってのは上下左右を海で囲われた陸の集まりだよ」
　と書いてあります。知らんけど

`ex
Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]Output: 3`

※島は下記のように３つあるってことですね。
  [<font color=red>"1","1"</font>,"0","0","0"],
  [<font color=red>"1","1"</font>,"0","0","0"],
  ["0","0",<font color=blue>"1"</font>,"0","0"],
  ["0","0","0",<font color=green>"1","1"</font>]

# 解法
実施時間：60分オーバー

```python
class Solution:
    
    def numIslands(self, grid: List[List[str]]) -> int: 
        def adjoining_land_check(grid,i,j):
            #確認前陸(1)かそれ以外（確認後陸(2)か海(0)）か判別
            if grid[i][j] == "1":
                #確認済み(2)に変更
                grid[i][j] = "2"
                #座標の上下左右が１なら2にしてその上も確認を繰り返す
                #上が存在するエリア
                if i-1>=0:
                    adjoining_land_check(grid,i-1,j)
                #右が存在するエリア
                if j-1>=0:
                    adjoining_land_check(grid,i,j-1)
                #下が存在するエリア
                if i+1<=len(grid)-1:
                    adjoining_land_check(grid,i+1,j)
                #左が存在するエリア
                if j+1<=len(grid[0])-1:
                    adjoining_land_check(grid,i,j+1)
        island_count = 0  
        #gridを左上〜右下まで横順で確認ループ
        for i,inner_grid in enumerate(grid):
            for j,area in enumerate(inner_grid):
                if grid[i][j] == "1":
                    #引数 グリッド grid 座標 var,hor (ij)
                    adjoining_land_check(grid,i,j)
                    #大陸数に+1
                    island_count +=1
        return island_count
```
※色々と余裕がなかったので汚いままですがご容赦を


# メイキング

```Python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        #gridを左上〜右下まで横順で確認ループ
            #確認前陸(1)かそれ以外（確認後陸(2)か海(0)）か判別
                #確認前陸(1)なら大陸数に+1
                #確認前陸(1)なら確認済み(2)に変更
                #上下左右が確認前陸(1)があれば確認済み(2)に変更してその上下左右もループ確認
            #2or0なら次を確認しに行く
```

とりあえずはざっと設計してみる。
肝は　#上下左右の確認〜　のところだなと思ったけども、
とりあえず詳細は後回しにしてコーディングしていくことに。

```python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        island_count = 0   
        for i,inner_grid in enumerate(grid):
            for j,area in enumerate(inner_grid):
                if area == "1":
                    island_count +=1
                    grid[i][j] = "2"
                    #上下左右が確認前陸(1)があれば確認済み(2)に変更してその上下左右もループ確認
                    
                    
                #2or0なら次を確認しに行く
        return island_count
```

25分程度で全体的には出来ました。
（この時点では　island_count　は単純に　"1"　の数を返します。）
それでは問題の箇所に入っていきます。まずは仮コーディングしてみる。

```
                    #上は1か？
                    　　#2にする
                    　　　　#さらに上は1か？
　　　　　　　　　　　　　　　　　#......
                    #右があるか？
                        #同じ感じ
                    #下があるか？
                        #同じ感じ
                    #左があるか？
                        #同じ感じ
```

際限なく確認せなあかんやろ。。。となるところです。1ヶ月前の自分では。
今は「再帰的」という言葉を知っているので余裕の予感がしましたが問題は時間。
（残り20分）

```python
class Solution:
    
    def numIslands(self, grid: List[List[str]]) -> int:
        island_count = 0   
        #gridを左上〜右下まで横順で確認ループ
        for i,inner_grid in enumerate(grid):
            for j,area in enumerate(inner_grid):
                #確認前陸(1)かそれ以外（確認後陸(2)か海(0)）か判別
                if area == "1":
                    #大陸数に+1
                    island_count +=1
                    
                    #確認済み(2)に変更
                    grid[i][j] = "2"
                    #上下左右が確認前陸(1)があれば確認済み(2)に変更してその上下左右もループ確認
                    #引数 グリッド grid 座標 var,hor (ij)
                    def adjoining_land_check(grid,i,j):
                        #座標の上下左右が１なら2にしてその上も確認を繰り返す
                        if grid[i-1][j] == "1":
                            grid[i-1][j] == "2"
                            adjoining_land_check(grid,i-1,j)
                        if grid[i][j+1] == "1":
                            grid[i][j+1] == "2"
                            adjoining_land_check(grid,i,j+1)
                        if grid[i+1][j] == "1":
                            grid[i+1][j] == "2"
                            adjoining_land_check(grid,i+1,j)
                        if grid[i][j-1] == "1":
                            grid[i][j-1] == "2"
                            adjoining_land_check(grid,i,j-1)
                    adjoining_land_check(grid,i,j)
                    print(grid)
                #2or0なら次を確認しに行く
        return island_count  
```
慣れない再帰処理とインナークラス実装で手こずりながらも完成しましたが。。。

<font color=red>Runtime Error
RecursionError: maximum recursion depth exceeded in comparison</font>


再帰エラー。。。だと。。。
と色々確認しているうちにタイムアップで、下記の記事を参考にさせて頂きました。


[LeetCode「200. Number of Islands」解説](https://qiita.com/wadayamada/items/c0ac42d1c323a975941d)

一番問題の箇所（エラー）は再帰の中の条件ですね。
早い話が確認範囲の際限がないため無限ループになっていたよう。

誤:

```python
if grid[i-1][j] == "1":
```

正:

```python
if i-1>=0:
```


後は、細々したところを直して完成。

今回は難易度Mediumってのもあったけど、再帰慣れないとだなぁ。。。