[LeetCode] 200. Number of Islands (Python)

• Reference
• visited 쓰고 풀 수도 있는 문제

Solution

from typing import List


class Solution:
    # 섬 -> '0'(water)로 둘러싸여 있어야 함, 보이지 않는 바깥은 전부 '0'이라고 가정
    # "대각선은 고려할 필요가 없음"
    def numIslands(self, grid: List[List[str]]) -> int:
        WATER = '0'
        LAND = '1'

        # answer: 섬의 개수
        answer = 0
        # 기본 x, y
        len_x = len(grid[0])
        len_y = len(grid)

        def dfs(x: int, y: int) -> None:
            if x < 0 or x >= len_x \
                    or y < 0 or y >= len_y \
                    or grid[y][x] == WATER:
                return

            # visited 사용할 수 있지만 공간복잡도를 위해 이 문제에서는 '0'으로 저장
            grid[y][x] = WATER

            dfs(x + 1, y)
            dfs(x - 1, y)
            dfs(x, y + 1)
            dfs(x, y - 1)

        for y in range(len_y):
            for x in range(len_x):
                if grid[y][x] == LAND:
                    dfs(x, y)
                    answer += 1

        return answer