[Leetcode 934] Shorted Bridge

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

1) 코드

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

        dx = [0, 0, -1, 1]
        dy = [1, -1, 0, 0]

        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    sx = i
                    sy = j

        stk = []
        stk.append([sx, sy])
        visited = set()

        while stk:
            x, y = stk.pop()
            visited.add((x, y))

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                
                if 0<=nx and nx<n and 0<=ny and ny<n and grid[nx][ny] and (nx,ny) not in visited:
                    stk.append([nx, ny])
                    visited.add((nx,ny))

        queue = list(visited)
        ans = 0 

        while queue:

            next_queue = [] 

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

                    if 0<=nx and nx<n and 0<=ny and ny<n and (nx,ny) not in visited:
                        if grid[nx][ny] == 1:
                            return ans 
                        next_queue.append([nx,ny])
                        visited.add((nx,ny))

            queue = next_queue
            ans += 1 

2) 해설

• DFS와 BFS를 조합해서 푸는 문제이다
  -> DFS로 한 섬의 좌표를 모두 visited에 저장해 둔 다음에
  그 좌표들을 queue로 변환해서 BFS를 타면 된다
  -> DFS를 탈 때, stack으로 DFS를 돌 수 있음을 알아야 한다.