[리트코드/Leetcode] 200 - Number of Islands

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.

📋 코드

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(visited, i, j):
            stack = []
            stack.append((i, j))
            visited[i][j] = True

            while stack:
                x, y = stack.pop()

                for i in range(4):
                    nx, ny = x + dx[i], y + dy[i]

                    if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] == '1' and not visited[nx][ny]:
                        stack.append((nx, ny))
                        visited[nx][ny] = True

        visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]

        result = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1' and not visited[i][j]:
                    dfs(visited, i, j)
                    result += 1

        return result

💡 한마디

섬의 개수 문제는 DFS 알고리즘의 기본 문제이다. DFS는 재귀로도 짤 수 있지만 stack을 이용한 반복문 형태로 풀어봤다.