0이 물을 나타내고 1이 땅을 나타내는 이진 행렬이 있다고 가정합니다. 섬은 4 방향으로 1을 연결하는 그룹입니다. 섬은 0(물) 또는 가장자리로 둘러싸여 있습니다. 두 섬을 연결하는 가장 짧은 다리의 길이를 찾아야 합니다.
따라서 입력이 다음과 같으면
| 0 | 0 | 1 |
| 1 | 0 | 1 |
| 1 | 0 | 0 |
그러면 출력은 1이 됩니다. 이것은 (1,0)에서 (1,2) 포인트에 연결됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
row :=행렬의 행 개수
-
col :=행렬의 열 개수
-
dfs() 함수를 정의합니다. 이것은 i, j, s가 걸립니다
-
(i, j)가 s에 있으면
-
반환
-
-
mat[i, j]가 0과 같으면
-
반환
-
-
(i, j)를 s
에 삽입 -
i - 1>=0이면
-
dfs(i - 1, j, s)
-
-
i + 1 <행이면
-
dfs(i + 1, j, s)
-
-
j - 1>=0이면
-
dfs(i, j - 1, s)
-
-
j + 1 <열이면
-
dfs(i, j + 1, s)
-
-
주요 방법에서 다음을 수행하십시오 -
-
본 :=새로운 세트
-
범위 0에서 행까지의 i에 대해 수행
-
본 크기> 0인 경우
-
루프에서 나오다
-
-
0에서 col 범위의 j에 대해 수행
-
mat[i, j]가 1과 같으면
-
dfs(i, j, 본)
-
루프에서 나오다
-
-
-
-
q :=이중 종료 큐
-
보이는 각 토지에 대해 수행
-
(i, j) :=땅
-
i - 1>=0이고 mat[i - 1, j]가 0과 같으면
-
q의 끝에 (i - 1, j, 1) 삽입
-
-
i + 1
-
q의 끝에 (i + 1, j, 1) 삽입
-
-
j - 1>=0이고 mat[i, j - 1]이 0과 같으면
-
q의 끝에 (i, j - 1, 1) 삽입
-
-
j + 1
-
q의 끝에 (i, j + 1, 1) 삽입
-
-
-
크기가 q> 0인 동안 수행
-
(i, j, dist) :=q의 왼쪽 항목, q 왼쪽부터 항목 삭제
-
(i, j)가 보이면
-
다음 반복으로 이동
-
-
보이는 대로 (i, j) 표시
-
mat[i, j]가 1과 같으면
-
반환 거리 - 1
-
-
i - 1>=0이면
-
q의 끝에 (i - 1, j, dist + 1) 삽입
-
-
i + 1 <행이 0이 아닌 경우
-
q의 끝에 (i + 1, j, dist + 1) 삽입
-
-
j - 1>=0이면
-
q의 끝에 (i, j - 1, dist + 1) 삽입
-
-
j + 1
-
q의 끝에 (i, j + 1, dist + 1) 삽입
-
-
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
import collections class Solution: def solve(self, mat): row = len(mat) col = len(mat[0]) def dfs(i, j, s): if (i, j) in s: return if mat[i][j] == 0: return s.add((i, j)) if i - 1 >= 0: dfs(i - 1, j, s) if i + 1 < row: dfs(i + 1, j, s) if j - 1 >= 0: dfs(i, j - 1, s) if j + 1 < col: dfs(i, j + 1, s) seen = set() for i in range(row): if len(seen) > 0: break for j in range(col): if mat[i][j] == 1: dfs(i, j, seen) break q = collections.deque() for land in seen: i, j = land if i - 1 >= 0 and mat[i - 1][j] == 0: q.append((i - 1, j, 1)) if i + 1 < row and mat[i + 1][j] == 0: q.append((i + 1, j, 1)) if j - 1 >= 0 and mat[i][j - 1] == 0: q.append((i, j - 1, 1)) if j + 1 < col and mat[i][j + 1] == 0: q.append((i, j + 1, 1)) while len(q) > 0: i, j, dist = q.popleft() if (i, j) in seen: continue seen.add((i, j)) if mat[i][j] == 1: return dist - 1 if i - 1 >= 0: q.append((i - 1, j, dist + 1)) if i + 1 < row: q.append((i + 1, j, dist + 1)) if j - 1 >= 0: q.append((i, j - 1, dist + 1)) if j + 1 < col: q.append((i, j + 1, dist + 1)) ob = Solution() matrix = [ [0, 0, 1], [1, 0, 1], [1, 0, 0], ] print(ob.solve(matrix))
입력
[ [0, 0, 1], [1, 0, 1], [1, 0, 0], ]
출력
1