200 Number of Islands

문제

Given an m x n 2d grid 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.

조건

예제

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

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

해결

1st

생각

코드

from typing import *

class Solution:
    grid: List[List[str]]

    def numIslands(self, grid: List[List[str]]) -> int:
        self.grid = grid
        ans = 0
        count = 0
        if not self.grid:
            return ans
        
        for i in range(len(self.grid)):  # i = m = 높이
            for j in range(len(self.grid[0])): # j = n = 너비
                if self.grid[i][j] == '1':
                    self.dfs(i, j)
                    count += 1
        return count
    
    def dfs(self, i, j):
        if i < 0 or i >= len(self.grid) or j < 0 or j >= len(self.grid[0]) or self.grid[i][j] != '1':
            return
        
        # 육지를 지워나간다
        self.grid[i][j] = '0'
        '''
        사실 배열에서 
        [ i
          0 => ["1", "1",...], j
          1 => ["1", "1",...], j
          2 => ["1", "1",...]  j
        ]
        i는 0,1,2,... 증가하면서 아래로 내려가므로, i가 증가할 때 남으로 간다고 보겠다
        '''
        self.dfs(i + 1, j) # i = m = 높이, i + 1 = 남으로
        self.dfs(i - 1, j) # i = m = 높이, i - 1 = 북으로
        self.dfs(i, j + 1) # j = n = 너비, j + 1 = 동으로
        self.dfs(i, j - 1) # j = n = 너비, j - 1 = 서로


s = Solution()

grid1 = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
print(s.numIslands(grid1))

grid2 = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
print(s.numIslands(grid2))