[리트코드] 0200. 섬 수

Python, C++, JavaScript, SQL 및 TypeScript의 다양한 LeetCode 솔루션을 살펴보세요. 여러 프로그래밍 언어로 인터뷰 준비, 학습 및 코드 연습에 적합합니다. Github 레포 링크

중간

주어진 xn 2D 바이너리 그리드 그리드 지도를 나타내는 것은 '1's(토지)와 '0's (물), 반환 섬의 수.

안 섬 는 물로 둘러싸여 있으며 인접한 토지를 수평 또는 수직으로 연결하여 형성됩니다. 그리드의 네 모서리가 모두 물로 둘러싸여 있다고 가정할 수 있습니다.

예시 1:

입력: 그리드 = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1 ","1","0","0","0"], ["0","0","0","0","0"] ]
산출: 1

예 2:

입력: 그리드 = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0 ","0","1","0","0"], ["0","0","0","1","1"] ]
산출: 3

제약:

m==그리드.길이
n == 그리드[i].길이
1 <= m, n <= 300
그리드[i][j] ~이다 '0' 또는 '1'.

파이썬

				
					# 시간 복잡도: O(m*n) # 공간 복잡도: O(m*n) 입력 가져오기 목록 클래스 솔루션: def dfs(self, Grid: List[List[str]], r: int, c: int) -> 없음: nR = len(grid) nC = len(grid[0]) Grid[r][c] = '0' if r - 1 >= 0 and Grid[r - 1][c] == " 1": self.dfs(grid, r - 1, c) if r + 1 < nR 및 Grid[r + 1][c] == "1": self.dfs(grid, r + 1, c) if c - 1 >= 0 및 그리드[r][c - 1] == "1": self.dfs(grid, r, c - 1) if c + 1 < nC 및 그리드[r][c + 1] == "1": self.dfs(grid, r, c + 1) def numIslands(self, Grid: List[List[str]]) -> int: 그리드가 아닌 경우 0 반환 numIslands = 0(범위 내 r에 대해) (len(grid)): for c in range(len(grid[0])): if Grid[r][c] == '1': numIslands += 1 self.dfs(grid, r, c) return numIslands 그리드 = [ ["1", "1", "0", "0", "0"], ["1", "1", "0", "0", "0"], [" 0", "0", "1", "0", "0"], ["0", "0", "0", "1", "1"] ] print(Solution().numIslands( 그리드))

중간

파이썬

관련 기사