Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

파이썬의 섬 수

<시간/>

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

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

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

세 개의 섬이 있습니다.

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

  • 두 가지 방법이 있습니다. 하나는 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이면 ​​이 메서드에서 반환
  • 그리드[i, j] =0이면 리턴, 그렇지 않으면 make grid[i, j] :=0
  • makeWater(i + 1, j, n, m, grid) 호출
  • makeWater(i, j + 1, n, m, grid) 호출

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

예시

class Solution(object):
   def numIslands(self, grid):
      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)
ob1 = Solution()
print(ob1.numIslands([["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],
["0","0","0","1","1"]]))

입력

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

출력

3