Python에서 두 개의 지도에서 겹치는 섬의 수를 계산하는 프로그램

두 개의 이진 행렬 mat1과 mat2가 있다고 가정합니다. 여기서 1은 육지, 0은 물을 나타내며, 1(육지)군이 물로 둘러싸여 있으면 섬이라고 합니다. 정확히 같은 좌표에서 mat1과 mat2에 존재하는 섬의 수를 찾아야 합니다.

따라서 입력이 mat1 =

그리고 mat2 =

겹치는 섬이 있기 때문에 출력은 2가 됩니다.

따라서 두 개의 겹치는 섬이 있습니다.

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

• r :=mat1의 행 수
• c :=mat1의 열 개수
• 마지막 행 :=r - 1
• last_col :=c - 1
• mark() 함수를 정의합니다. i, j
• mat1[i, j] :=0
• mat2[i, j] :=0
• i가 0이 아니고 (mat1[i - 1, j] 또는 mat2[i - 1, j] 중 하나가 0이 아닌 경우),
  • 표시(i - 1, j)
• j가 0이 아니고 (mat1[i, j - 1] 또는 mat2[i, j - 1] 중 하나가 0이 아닌 경우)
  • 표시(i, j - 1)
• j
• 표시(i, j + 1)

예

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

def solve(mat1, mat2):
   r = len(mat1)
   c = len(mat1[0])
   last_row = r - 1
   last_col = c - 1

   def mark(i, j):
      mat1[i][j] = mat2[i][j] = 0
      if i and (mat1[i - 1][j] or mat2[i - 1][j]):
         mark(i - 1, j)
      if j and (mat1[i][j - 1] or mat2[i][j - 1]):
         mark(i, j - 1)
      if j < last_col and (mat1[i][j + 1] or mat2[i][j + 1]):
         mark(i, j + 1)
      if i < last_row and (mat1[i + 1][j] or mat2[i + 1][j]):
         mark(i + 1, j)

   for i in range(r):
      for j in range(c):
         if mat1[i][j] != mat2[i][j]:
            mark(i, j)

   islands = 0
   for i in range(r):
      for j in range(c):
         if mat1[i][j]:
            islands += 1
            mark(i, j)
   return islands

mat1 = [
[1, 0, 1],
[1, 0, 0],
[1, 0, 1]
]
mat2 = [
[1, 0, 1],
[1, 0, 0],
[1, 0, 0]
]
print(solve(mat1, mat2))

입력

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

출력

2