2023.05.21 Today's Challenge

https://leetcode.com/problems/shortest-bridge/

Shortest Bridge - LeetCode

BFS / DFS로 푸는 문제.

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid)
        fx, fy = -1, -1

        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    fx, fy = i, j
                    break

        def dfs(x, y):
            grid[x][y] = 2
            q.append((x,y))
            for cx, cy in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
                if 0 <= cx < n and 0 <= cy < n and grid[cx][cy] == 1:
                    dfs(cx, cy)
        
        q = []
        dfs(fx, fy)
        
        d = 0
        while q:
            nb = []
            for x, y in q:
                for cx, cy in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)] :
                    if 0 <= cx < n and 0 <= cy < n:
                        if grid[cx][cy] == 1:
                            return d
                        elif grid[cx][cy] == 0:
                            nb.append((cx, cy))
                            grid[cx][cy] = -1
            q = nb
            d += 1