Python에서 주어진 행렬의 섬 수를 계산하는 프로그램

이진 행렬이 있다고 가정하고 행렬에서 섬의 ​​수를 찾아야 합니다. 여기서 1은 육지이고 0은 물입니다. 따라서 섬은 이웃하고 주변이 물로 둘러싸인 1의 그룹입니다. 여기서 우리는 이웃이 대각선이 아닌 수평 또는 수직만 될 수 있다고 생각합니다.

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

그러면 출력은 4가 됩니다.

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

• explore() 함수를 정의합니다. 행, 열, 행렬이 필요합니다.
• 행과 열이 행렬의 범위에 있지 않거나 행렬[row, col]이 0이면
  • 반환
• 행렬, 열] :=0
• 탐색(행 + 1, 열, 행렬)
• 탐색(행 - 1, 열, 행렬)
• 탐색(행, 열 + 1, 행렬)
• 탐색(행, 열 - 1, 행렬)
• 메인 방법에서 다음을 수행하십시오. -
• 행렬이 null이면
  • 0을 반환
• 섬:=0
• 행렬 0에서 행렬의 행 수까지 범위에 있는 행에 대해
  • 행렬의 열 개수에 대한 범위 0의 열에 대해
    • 행렬[row, col]이 1이면
      • 섬 :=섬 + 1
      • 탐색(행, 열, 행렬)
• 리턴 아일랜드

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

예

class 솔루션:def explore(self, row, col, matrix):if ( row <0 or col <0 or row> len(matrix) - 1 or col> len (matrix[0]) - 1 or matrix [row][col] ==0):return matrix[row][col] =0 self.explore(row + 1, col, matrix) self.explore(row - 1, col, matrix) self.explore(row , col + 1, matrix) self.explore(row, col - 1, matrix) def solve(self, matrix):행렬이 아닌 경우:return 0 island =0 for row in range(len(matrix)):for col in range(len(matrix[0])):행렬[row][col] ==1인 경우:섬 +=1 self.explore(행, 열, 행렬) 반환 islandob =Solution() 행렬 =[ [1, 0 , 1, 0, 0], [0, 0, 1, 0, 0], [0, 1, 1, 0, 0], [0, 0, 0, 0, 0], [1, 1, 0 , 1, 1], [1, 1, 1, 0, 1]]print(ob.solve(매트릭스))

입력

출력

4