엔지니어 게시판
LeetCode 솔루션 분류

[8/29] 200. Number of Islands

컨텐츠 정보

본문

200. Number of Islands
Medium
15918371Add to ListShare

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.

 

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.
Accepted
1,771,851
Submissions
3,206,958

관련자료

댓글 1

학부유학생님의 댓글

  • 익명
  • 작성일
Runtime: 517 ms, faster than 43.44% of Python3 online submissions for Number of Islands.
Memory Usage: 25.1 MB, less than 12.15% of Python3 online submissions for Number of Islands.
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        island_count = 0
        
        visited = set()
        
        ROW, COL = len(grid), len(grid[0])
        directions = [[1,0],[0,1],[-1,0],[0,-1]]
        
        
        def dfs(row, col):
            if row >= ROW or col >= COL or row < 0 or col < 0 or (row,col) in visited or grid[row][col] == "0":
                return
            
            visited.add((row,col))
            
            for row_dir, col_dir in directions:
                dfs(row + row_dir, col + col_dir)
            
        
        for i in range(ROW):
            for j in range(COL):
                if (i,j) not in visited and grid[i][j] == "1":
                    dfs(i,j)
                    island_count += 1
        
        return island_count
전체 404 / 2 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 943 명
  • 오늘 방문자 5,561 명
  • 어제 방문자 6,932 명
  • 최대 방문자 14,831 명
  • 전체 회원수 1,481 명
알림 0