파이썬에서 행렬에서 가장 큰 섬의 면적을 찾는 프로그램

이진 행렬이 있다고 가정합니다. 여기서 1은 육지를, 0은 물을 나타내며, 섬은 주변이 물로 둘러싸여 있는 이웃한 1의 그룹입니다. 매트릭스의 가장자리가 물로 둘러싸여 있다고 가정할 수 있습니다. 행렬에서 가장 큰 섬의 면적을 찾아야 합니다.

따라서 입력이 다음과 같으면

그러면 출력은 6이 됩니다.

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

• dfs() 함수를 정의합니다. 행렬, r, c
가 필요합니다.
• 총계 :=총계 + 1
• 행렬[r, c] :=0
• r - 1>=0이고 행렬[r - 1, c]이 1과 같으면
  • dfs(행렬, r - 1, c)
• c - 1>=0이고 행렬[r, c - 1]이 1과 같으면
  • dfs(행렬, r, c - 1)
• r + 1
• dfs(행렬, r + 1, c)

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

예시

class Solution:
   def solve(self, matrix):
      self.r_len = len(matrix)
      self.c_len = len(matrix[0])
      max_island = 0
      for r in range(self.r_len):
         for c in range(self.c_len):
            if matrix[r][c] == 1:
               self.total = 0
               self.dfs(matrix, r, c)
               max_island = max(max_island, self.total)
      return max_island
   def dfs(self, matrix, r, c):
      self.total += 1
      matrix[r][c] = 0
      if r - 1 >= 0 and matrix[r - 1][c] == 1:
         self.dfs(matrix, r - 1, c)
      if c - 1 >= 0 and matrix[r][c - 1] == 1:
         self.dfs(matrix, r, c - 1)
      if r + 1 < self.r_len and matrix[r + 1][c] == 1:
         self.dfs(matrix, r + 1, c)
      if c + 1 < self.c_len and matrix[r][c + 1] == 1:
         self.dfs(matrix, r, c + 1)
ob = Solution()
matrix = [ [0, 0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1, 0] ]
print(ob.solve(matrix))

입력

matrix = [
[0, 0, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 0, 0],
[0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 1, 0] ]

출력

6