Python의 2D 행렬에서 고유한 섬의 수 찾기

이진 행렬이 있다고 가정합니다. 우리는 그 안에 있는 섬의 수를 세어야 합니다. 섬은 물로 둘러싸여 있고 인접한 육지를 수평 또는 수직으로 연결하여 형성된 곳입니다. 그리드의 네 모서리가 모두 물로 둘러싸여 있다고 가정할 수 있습니다.

그리드가 다음과 같다고 가정합니다 -

3개의 섬이 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 두 가지 방법이 있습니다. 하나는 numIslands() 및 makeWater()라는 섬의 수를 계산하는 데 사용됩니다. makeWater()는 다음과 같습니다 -

• 그리드의 행 수가 0이면 0을 반환합니다.

• n =행 개수 및 m :=열 개수, ans :=0

• 0 ~ n – 1 범위의 i에 대해

  • 범위 0에서 m까지의 j에 대해

    • 그리드[i, j] =1이면 ans :=ans + 1

    • makeWater(i, j, n, m, 그리드)

• makeWater()는 인덱스 i, j, 행 및 열 개수 n 및 m, 그리드를 사용합니다.

• i <0 또는 j <0 또는 i>=n 또는 j>=m이면 ​​이 메서드에서 반환

• grid[i, j] =0이면 리턴, 그렇지 않으면 make grid[i, j] :=0

• makeWater(i + 1, j, n, m, 그리드) 호출

• makeWater(i, j + 1, n, m, grid) 호출

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution(object):
   def numIslands(self, grid):
      """
      :type grid: List[List[str]]
      :rtype: int
      """
      if len(grid) == 0:
         return 0
      n= len(grid)
      m = len(grid[0])
      ans = 0
      for i in range(n):
         for j in range(m):
            if grid[i][j] == "1":
               ans+=1
            self.make_water(i,j,n,m,grid)
         return ans
   def make_water(self,i,j,n,m,grid):
      if i<0 or j<0 or i>=n or j>=m:
         return
      if grid[i][j] == "0":
         return
      else:
         grid[i][j]="0"
      self.make_water(i+1,j,n,m,grid)
      self.make_water(i,j+1,n,m,grid)
      self.make_water(i-1,j,n,m,grid)
      self.make_water(i,j-1,n,m,grid)

입력

[["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]]

출력

3