파이썬에서 떠날 수 없는 섬의 수를 찾는 프로그램

이진 행렬이 있다고 가정합니다. 여기서 1은 육지를 나타내고 0은 물을 나타냅니다. 모든 땅에서 우리는 위, 아래, 왼쪽 또는 오른쪽으로 이동할 수 있지만 대각선으로 다른 땅 셀로 이동하거나 매트릭스에서 벗어날 수 없습니다. 매트릭스에서 벗어날 수 없는 육지 세포의 수를 찾아야 합니다.

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

그러면 출력은 4가 됩니다. 중앙에 4개의 사각형이 있기 때문에 매트릭스에서 벗어날 수 없습니다.

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

• q :=행렬[i, j]가 랜드 i이고 j가 경계 인덱스일 때 각 행 i와 열에 대한 쌍(i, j)의 목록
• idx :=0
• q의 각 쌍(x, y)에 대해 수행
  • 행렬[x, y] :=0
• idx
• x, y :=q[idx]
• [(-1, 0) ,(0, -1) ,(0, 1) ,(1, 0) ]의 각 (dx, dy)에 대해, do
  • nx :=x + dx
  • ny :=y + dy
  • 만약 0 <=nx <행렬의 행 개수 및 0 <=ny <행렬[nx] 및 행렬[nx, ny]의 열 개수가 1이면
    • 행렬[nx, ny] :=0
    • q 끝에 (nx, ny) 삽입
• idx :=idx + 1

예

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

def solve(matrix):
   q = [(i, j) for i in range(len(matrix)) for j in range(len(matrix[i])) if matrix[i][j] and (i == 0 or i == len(matrix) - 1 or j == 0 or j == len(matrix[i]) - 1)]
   idx = 0
   for x, y in q:
      matrix[x][y] = 0
   while idx < len(q):
      x, y = q[idx]
      for dx, dy in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
         nx, ny = x + dx, y + dy
         if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[nx]) and matrix[nx][ny]:
            matrix[nx][ny] = 0
            q.append((nx, ny))
      idx += 1
   return sum(sum(row) for row in matrix)

matrix = [
[0, 0, 0, 1],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 1]
]
print(solve(matrix))

입력

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

출력

4