LeetCode 솔루션

[8/29] 200. Number of Islands

학부유학생 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.08.28 17:34

6,723 조회
1 댓글
0 추천
0 비추천
목록 게시글 쓰기

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

#Amazon, #Microsoft, #Bloomberg, #Google, #Facebook, #Apple, #Uber, #LinkedIn, #tiktok, #DoorDash, #Oracle, #Adobe, #Paypal, #ByteDance, #Walmart Global Tech, #Twitch, #Intuit, #Shopee, #eBay, #Snapchat

링크

https://leetcode.com/problems/number-of-islands/ 2743 회 연결

익명
작성일 2022.08.28 17:34

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

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.
[code=Python 3]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[/code]