1이 육지를 나타내고 0이 물을 나타내는 이진 행렬이 있다고 가정합니다. 그리고 섬은 0(물) 또는 가장자리로 둘러싸인 1의 그룹입니다. 완전히 물로 둘러싸인 모든 섬을 찾아 0으로 수정해야 합니다. 우리가 알고 있듯이 모든 이웃(대각선이 아닌 수평 및 수직)이 0(이웃 중 어느 것도 가장자리가 아님)이면 섬은 물로 둘러싸여 완성됩니다.
따라서 입력이 다음과 같으면
| 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 |
그러면 출력은
| 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 |
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
row :=A의 행 수
-
col :=A의 열 개수
-
B :=크기가 A이고 0으로 채워지는 행렬
-
본 :=새로운 세트
-
범위 0에서 행까지의 i에 대해 수행
-
0에서 col 범위의 j에 대해 수행
-
i와 j가 행렬의 범위에 없으면
-
다음 반복으로 이동
-
-
(i, j)가 보이면
-
다음 반복으로 이동
-
-
A[i, j]가 0과 같으면
-
다음 반복으로 이동
-
-
d :=하나의 요소(i, j)가 있는 이중 종료 큐
-
d가 비어 있지 않은 동안 수행
-
(x, y) :=d의 왼쪽 요소, d에서 삭제
-
B[x, y] :=1
-
(x, y)의 각 이웃(x2, y2)에 대해 수행
-
(x2, y2)가 보이지 않으면
-
d
끝에 (x2, y2) 삽입 -
보이는 대로 (x2, y2) 표시
-
-
-
-
-
-
B를 반환
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
from collections import deque class Solution: def solve(self, A): row = len(A) col = len(A[0]) B = [[0 for _ in range(col)] for _ in range(row)] seen = set() def nei(i, j): if i + 1 < row and A[i + 1][j]: yield (i + 1, j) if j + 1 < col and A[i][j + 1]: yield (i, j + 1) if i - 1 >= 0 and A[i - 1][j]: yield (i - 1, j) if j - 1 >= 0 and A[i][j - 1]: yield (i, j - 1) for i in range(row): for j in range(col): if i not in (0, row - 1) and j not in (0, col - 1): continue if (i, j) in seen: continue if A[i][j] == 0: continue d = deque([(i, j)]) while d: x, y = d.popleft() B[x][y] = 1 for x2, y2 in nei(x, y): if (x2, y2) not in seen: d.append((x2, y2)) seen.add((x2, y2)) return B ob = Solution() matrix = [ [1, 0, 0, 0], [0, 1, 1, 0], [0, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 1], ] print(ob.solve(matrix))
입력
[ [1, 0, 0, 0], [0, 1, 1, 0], [0, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 1], ]
출력
[ [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 1] ]