Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 두 섬을 잇는 최단 다리 길이 찾기

0은 물을, 1은 육지를 나타내는 이진 행렬(binary matrix)이 주어졌다고 가정해 봅시다. 여기서 섬(island)이란 상하좌우 4방향으로 서로 연결된 1들의 묶음을 의미하며, 모든 섬은 물(0) 또는 행렬의 가장자리에 의해 둘러싸여 있습니다. 우리가 구해야 할 것은 두 섬을 연결하는 가장 짧은 다리의 길이입니다.

문제 예시

예를 들어 다음과 같은 입력이 주어진다고 해보겠습니다.

001
101
100

이 경우 출력 결과는 1이 됩니다. 즉, 좌표 (1,0)에 있는 섬과 좌표 (1,2)에 있는 섬을 다리 하나로 연결할 수 있다는 뜻입니다.

풀이 접근 방법

이 문제는 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)를 함께 사용하면 효율적으로 해결할 수 있습니다. 전체적인 흐름은 다음과 같습니다.

1단계: DFS로 첫 번째 섬 찾기

  • 행(row)과 열(col)의 개수를 구합니다.
  • dfs() 함수를 정의합니다. 이 함수는 i, j, s(방문 집합)를 인자로 받습니다.
  • (i, j)가 이미 s에 있으면 종료합니다.
  • mat[i][j]가 0(물)이면 종료합니다.
  • (i, j)를 s에 추가하고, 경계를 벗어나지 않는 범위에서 상하좌우 방향으로 재귀적으로 dfs를 호출합니다.

2단계: 첫 번째 섬의 가장자리에서 BFS 시작

  • seen이라는 새로운 집합을 만들고, 행렬을 순회하며 처음 발견한 1에서 dfs를 호출해 첫 번째 섬 전체를 seen에 저장합니다.
  • 덱(deque)을 생성한 뒤, seen에 속한 모든 육지 칸의 인접한 물 칸(0)을 큐에 거리(dist) = 1과 함께 삽입합니다.

3단계: BFS로 두 번째 섬까지 확장

  • 큐가 빌 때까지 왼쪽에서 요소를 꺼냅니다.
  • 이미 방문한 좌표라면 건너뜁니다.
  • 현재 좌표를 seen에 추가합니다.
  • 만약 mat[i][j]가 1(두 번째 섬의 육지)이라면 dist - 1을 반환합니다. 다리는 물 칸 위에만 놓이므로 마지막 육지 칸까지의 거리에서 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

마무리

이 알고리즘은 DFS를 통해 첫 번째 섬의 모든 좌표를 파악한 후, 해당 섬의 경계에서 BFS를 시작하여 두 번째 섬에 도달하는 최소 거리를 계산합니다. 시간 복잡도는 O(N×M)(N은 행의 수, M은 열의 수)이며, 각 칸을 최대 한 번씩만 방문하므로 매우 효율적입니다.