파이썬에서 행렬의 둘러싸인 섬 수를 계산하는 프로그램

이진 행렬이 있다고 가정합니다. 여기서 1은 육지를 나타내고 0은 물을 나타냅니다. 우리가 알다시피 섬은 주변이 물로 둘러싸인 함께 그룹화 된 1의 그룹입니다. 완전히 둘러싸인 섬의 수를 찾아야 합니다.

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

세 개의 섬이 있기 때문에 출력은 2가 되지만 그 중 두 개는 완전히 둘러싸여 있습니다.

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

• dfs() 함수를 정의합니다. i, j
• i와 j가 행렬의 범위가 아니면
  • 거짓을 반환
• 행렬[i,j]가 0과 같으면
  • 참 반환
• 행렬[i, j] :=0
• a :=dfs(i + 1, j)
• b :=dfs(i - 1, j)
• c :=dfs(i, j + 1)
• d :=dfs(i, j - 1)
• a와 b, c와 d를 반환
• 기본 방법에서 다음을 수행합니다.
• R :=행렬의 행 개수, C :=행렬의 열 개수
• ans :=0
• 0~R 범위의 i에 대해 다음을 수행합니다.
  • 0~C 범위의 j에 대해 다음을 수행합니다.
    • 행렬[i,j]가 1과 같으면
      • dfs(i, j)가 참이면
        • ans :=ans + 1
• 반환

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

예시

class Solution:
   def solve(self, matrix):
      def dfs(i, j):
         if i < 0 or j < 0 or i >= R or j >= C:
            return False
         if matrix[i][j] == 0:
            return True
         matrix[i][j] = 0
         a = dfs(i + 1, j)
         b = dfs(i - 1, j)
         c = dfs(i, j + 1)
         d = dfs(i, j - 1)
         return a and b and c and d

      R, C = len(matrix), len(matrix[0])
      ans = 0
      for i in range(R):
         for j in range(C):
            if matrix[i][j] == 1:
               if dfs(i, j):
                  ans += 1
      return ans

ob = Solution()
matrix = [
   [1, 0, 0, 0, 0],
   [0, 0, 0, 1, 0],
   [0, 1, 0, 0, 0],
   [0, 1, 0, 0, 0],
   [0, 1, 1, 1, 0],
   [0, 0, 0, 0, 0]
]
print(ob.solve(matrix))

입력

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

출력

2