섬의 수

'1'(땅)과 '0'(물)의 지도를 나타내는 m x n 2D 이진 그리드 그리드가 주어지면 섬의 수를 반환합니다.

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

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """

        if not grid: 
            return 0

        rows, cols = len(grid), len(grid[0])

        islands = 0
        visited = set()

        def bfs(r, c):
            q = collections.deque()
            visited.add((r, c))
            q.append((r, c))

            while q: 
                row, col = q.pop()
                directions = [
                    [1, 0], [-1, 0],
                    [0, 1], [0, -1]
                ]
                for dr, dc in directions: 
                    if(
                        (r + dr) in range(rows) 
                        and (c + dc) in range(cols)
                        and grid[r+dr][c+dc] == "1" 
                        and (r+dr, c+dc) not in visited

                    ):
                        visited.add((r+dr, c+dc))
                        q.append((r+dr, c+dc))
                        bfs(r+dr, c+dc)



        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1" and (r, c) not in visited:
                    bfs(r, c)
                    islands += 1


        return islands 







좋은 웹페이지 즐겨찾기