200. Number of Islands

문제 링크 : https://leetcode.com/problems/number-of-islands/description/

주어진 grid에서 island(1이 모여있는거)가 몇개 있는지 묻는 문제이다.

grid를 탐색하며 만약에 1이면 주변에도 1인지 탐색하는 dfs를 연습하기 매우 좋은 문제이다.

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        row = len(grid)
        col = len(grid[0])
        cnt, visited = 0, set()
        
        def dfs(grid, i, j, visited):
            if i<0 or i >=row or j<0 or j>=col or grid[i][j] != "1" or (i,j) in visited:
                return
            visited.add((i,j))
            dfs(grid, i+1, j, visited)
            dfs(grid, i-1, j, visited)
            dfs(grid, i, j+1, visited)
            dfs(grid, i, j-1, visited)

        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1" and (i,j) not in visited:
                    cnt +=1
                    dfs(grid, i ,j , visited)
        return cnt