2차원 이진 행렬이 있다고 가정하고 주어진 행렬에서 고유한 섬의 수를 찾아야 합니다. 여기서 1은 육지를 나타내고 0은 물을 나타내므로 섬은 주변이 물로 둘러싸여 있는 1의 집합입니다. 모양이 다른 두 개의 섬은 고유합니다.
따라서 입력이 다음과 같으면
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
그러면 출력은 4가 됩니다(별도의 섬은 다른 색상으로 표시됨).
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
dfs() 함수를 정의합니다. i, j, k, l
-
매트[i, j] :=0
-
모양 끝에 쌍(i − k, j − l) 삽입
-
i + 1
-
dfs(i + 1, j, k, l)
-
-
j + 1
-
dfs(i, j + 1, k, l)
-
-
i − 1>=0이고 mat[i − 1, j]가 1이면
-
dfs(i − 1, j, k, l)
-
-
j − 1>=0이고 mat[i, j − 1]이 1이면
-
dfs(i, j − 1, k, l)
-
-
주요 방법에서 다음을 수행하십시오 -
-
cnt :=0
-
모양 :=새로운 세트
-
매트의 행 수까지 범위 0에 있는 i에 대해
-
mat의 열 개수까지 범위 0의 j에 대해
-
mat[i, j]가 1이면
-
모양 :=새 목록
-
dfs(i, j, i, j)
-
모양이 모양에 없으면
-
cnt :=cnt + 1
-
-
도형에 도형 삽입
-
-
-
-
반환 cnt
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def solve(self, mat): def dfs(i, j, k, l): mat[i][j] = 0 shape.append((i − k, j − l)) if i + 1 < len(mat) and mat[i + 1][j]: dfs(i + 1, j, k, l) if j + 1 < len(mat[0]) and mat[i][j + 1]: dfs(i, j + 1, k, l) if i − 1 >= 0 and mat[i − 1][j]: dfs(i − 1, j, k, l) if j − 1 >= 0 and mat[i][j − 1]: dfs(i, j − 1, k, l) cnt = 0 shapes = set() for i in range(len(mat)): for j in range(len(mat[0])): if mat[i][j]: shape = [] dfs(i, j, i, j) shape = tuple(shape) if shape not in shapes: cnt += 1 shapes.add(shape) return cnt ob = Solution() matrix = [ [1, 0, 0, 0, 0], [1, 0, 1, 0, 1], [0, 1, 1, 0, 1], [0, 0, 1, 0, 0], [1, 0, 0, 0, 0], [1, 1, 0, 1, 1] ] print(ob.solve(matrix))
입력
[ [1, 0, 0, 0, 0], [1, 0, 1, 0, 1], [0, 1, 1, 0, 1], [0, 0, 1, 0, 0], [1, 0, 0, 0, 0], [1, 1, 0, 1, 1] ]
출력
4