#31 [파이썬] LeetCode: Number of Islands

https://leetcode.com/problems/number-of-islands/

Number of Islands - LeetCode

 

---

 

코드

 

class Solution:
    def dfs(self, grid: List[List[str]], i: int, j: int):
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
                return
            
            grid[i][j] = '0'
            self.dfs(grid, i + 1, j)
            self.dfs(grid, i - 1, j)
            self.dfs(grid, i, j + 1)
            self.dfs(grid, i, j - 1)
            
    def numIslands(self, grid: List[List[str]]) -> int:
        cnt = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    cnt += 1
        return cnt

 

---

 

• 수직, 수평으로 연결된 노드를 탐색하며 하나의 섬을 찾을 수 있다. 따라서 dfs 또는 bfs를 사용할 수 있으며, 한 번의 재귀에서 하나의 섬을 찾을 수 있다.
• 수직 또는 수평으로 연결된 노드를 탐색하기 위해 현재 노드를 기준으로 상, 하, 좌, 우를 탐색하여 '1'일 경우 탐색을 이어나간다. '0'일 경우 탐색을 멈춘다.
• 가장자리의 경우 '0'으로 패딩을 줄 수도 있고, 아래의 조건식으로 탐색을 제한할 수 있다.

if if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]):

• 객체 내의 함수를 정의할 때는 첫번째 인자에 self를 반드시 포함해야 하며, 함수를 호출할 때는 함수명 앞에 self.를 붙여 호출해야 한다.