LeetCode 솔루션 분류
[8/29] 200. Number of Islands
본문
200. Number of Islands
Medium
15918371Add to ListShareGiven 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
관련자료
-
링크
댓글 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.
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