Leetcode 섬 수

이 게시물에서는 Number Of Islands라는 이름의 LeetCode problem #200을 살펴보겠습니다.

문제 설명은 매우 간단합니다. 1과 0의 격자가 주어지면 주어진 격자에서 총 섬 수를 찾아야 합니다.

그들은 다음을 언급합니다.

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.

예를 들어:

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

또 다른 예:

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

어떻게 해결합니까?

내 접근 방식은 그리드의 각 (방문하지 않은) 셀을 보는 것입니다. 1을 포함하는 경우 이웃도 1을 갖는 한 (재귀적으로) 바깥쪽으로 확장합니다. 이를 BFS(폭 우선 검색)라고 합니다.

셀을 방문하면 나중에 다시 방문하지 않도록 해당 셀을 방문한 것으로 표시합니다.

해결책은 다음과 같습니다.

class Solution:
    def numIslands(self, grid):

        ROWS, COLS = len(grid), len(grid[0])
        res = 0
        visited = set()

        def dfs(r,c):
            if r<0 or c<0 or r>=ROWS or c>=COLS or (r,c) in visited or grid[r][c] != "1":
                return

            visited.add((r,c))
            dfs(r+1,c)
            dfs(r-1,c)
            dfs(r,c+1)
            dfs(r,c-1)

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == "1" and (r,c) not in visited:
                    res += 1
                    dfs(r,c)

        return res

코드 자체도 매우 이해하기 쉽습니다. 도움이 되셨기를 바랍니다.

단순히 # 기호와 같은 기호로 1을 표시하여 방문 세트 사용을 피할 수 있습니다.

--
Unsplash에 있는 Sacha Gregoire의 표지 사진