200 Number of Islands

• 200 Number of Islands
  • 문제
  • 조건
  • 예제
  • 해결
    • 1st
      • 생각
      • 코드

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.

조건

• m == grid.length
• n == grid[i].length
• $1 \le m, n \le 300$
• grid[i][j] is ‘0’ or ‘1’.

예제

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

생각

• 주어진 데이터
  • m = grid.length = 지도의 높이
  • n = grid[i].length = 지도의 너비
  • 1: 섬
  • 0: 물
• 어떻게 섬을 셀 수 있을까?
  • 생각을 못해내서 결국 문제 풀이를 참고 했다
  • 1이 있는 것들을 어떻게 세지?라고 생각을 했지만, 연결되어 있는 1을 없애 나가도 되는구나! 이런 생각은 어떻게 하지?
  • 처음에는 문제가 “섬의 개수를 구하라”라는 것이라고 해서, 코드로도 count 한다고 생각했는데, 그러지 않아도 문제는 해결 됐다.
  • “무엇무엇을 구하라”, 라는 문장은 중요하지 않다. 문제를 해결해 나갈 방식의 관점에서 생각할 필요가 있는 거 같다.

코드

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))

• 기저 조건
  • i < 0 or i >= len(self.grid): 음수든 양수든 지도 높이의 범위 초과
  • j < 0 or j >= len(self.grid[0]): 음수든 양수든 지도 너비의 범위 초과
  • self.grid[i][j] != ‘1’: 땅을 지워나가므로, 땅이 아닌 경우 종료