[Leetcode Medium] 934. Shortest Bridge

 

You are given an n x n binary matrix grid where 1 represents land and 0 represents water.

An island is a 4-directionally connected group of 1's not connected to any other 1's. There are exactly two islands in grid.

You may change 0's to 1's to connect the two islands to form one island.

Return the smallest number of 0's you must flip to connect the two islands.

 

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 1

Example 2:

Input: grid = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

Example 3:

Input: grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

 

Constraints:

• n == grid.length == grid[i].length
• 2 <= n <= 100
• grid[i][j] is either 0 or 1.
• There are exactly two islands in grid.

---

Leetcode 스터디 문제를 가지고 와봤습니다!

 

모든 정점이 0 또는 1로 이뤄져있으므로, 가중치가 0 또는 1인 간선으로 이어진 그래프 문제로 바라볼 수 있겠습니다.

이를 이용해 0-1 BFS를 진행하며 현재의 땅까지 오기 위해 물을 총 얼마나 지나야하는지에 대한 최단거리를 갱신하면

됩니다.

 

단, 현재까지의 거리 코스트가 0인경우는 동일한 섬에 위치한 땅이므로 결과갱신에서 제외하는것에 유의해야합니다.

 

from typing import List
from collections import deque

class Solution:
    def ZeroOneBFS(self, grid: List[List[int]]) -> int:
        dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
        dp = [[float("inf")] * len(grid) for _ in range(len(grid))]
        visit = [[False] * len(grid) for _ in range(len(grid))]
        queue = deque()

        minCost = float("inf")

        while queue:
            x,y = queue.popleft()
            if visit[x][y]: continue
            visit[x][y] = True

            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]

                if not(0 <= nx < len(grid) and 0 <= ny < len(grid) and dp[nx][ny] <= dp[x][y]):  continue

                dp[nx][ny] = dp[x][y] + 1 - grid[nx][ny]

                if grid[nx][ny]:
                    queue.appendleft((nx, ny))
                    minCost = max(minCost,dp[nx][ny])
                else:
                    queue.append((nx,ny))