[LEET CODE] 200. Number of Islands

# Problem

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.     Constraints: m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j] is '0' or '1'.

1. 값이 1인 부분의 상,하,좌,우 연결된 부분 확인

2. 연결된 육지 부분을 다 돌고 빠져나왔을 때 +1 

3. 다음으로 넘어갈때 이미 센 부분은 넘어가야함 - 처음에 돌때 값을 육지가 아닌 값으로 바꿔주기

 

# Solution 1

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(i, j):
            # 더 이상 땅이 아닌 경우 종료
            if i < 0 or i >= len(grid) or \
                    j < 0 or j >= len(grid[0]) or \
                    grid[i][j] != '1':
                return

            grid[i][j] = 0 # 한번 확인한 육지는 0으로 바꿔서 다음에 육지로 인식 못하게 한다

            # 동서남북 탐색
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)

        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    dfs(i, j)
                    # 모든 육지 탐색 후 카운트 1 증가
                    count += 1
        return count

dfs를 중첩 함수로 썼기 때문에 numIslands의 변수들도 dfs 함수 안에서 사용 가능 

---

# 중첩 함수 ( Nested Function )

함수 내에 위치한 또 다른 함수

부모 함수의 변수를 자유롭게 읽을 수 있다.

가변 객체의 경우 append, pop 등 연산 조작 가능

! 재할당의 경우에는 참조 ID가 변경되어 별도의 로컬 변수로 선언되므로 주의 필요