[리트코드 1254] 닫힌 섬의 개수 — 경계에서 BFS로 열린 섬을 먼저 제거

원제: Number of Closed Islands

문제 요약

0은 땅, 1은 물이며, 상하좌우로 연결된 0의 최대 그룹 하나를 섬 하나로 봅니다. 모든 방향에서 1로 둘러싸인 닫힌 섬의 개수를 반환합니다.

조건과 입출력

grid는 0과 1로 이루어진 2차원 배열이며, 1 <= grid.length, grid[0].length <= 100, 0 <= grid[i][j] <= 1입니다. 연결은 대각선을 제외한 상하좌우만 인정합니다.

예제와 문제 자료

원문 예제 2: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]], 반환값은 1입니다. 가장자리와 연결된 0 그룹은 닫힌 섬이 아니며, 가운데 (1,2)의 0만 사방이 1이므로 닫힌 섬입니다.

풀이 아이디어

가장자리의 땅과 연결된 섬은 바깥으로 열려 있으므로 닫힌 섬이 될 수 없습니다. 코드에서는 먼저 모든 가장자리 칸을 확인해, 아직 방문하지 않은 0에서 BFS를 실행하고 그 연결 요소를 visited로 표시합니다. 이후 내부 칸을 순회하면서 방문하지 않은 0을 발견하면 그 연결 요소는 가장자리와 이어지지 않은 섬입니다. 이때 BFS로 섬 전체를 방문 처리한 뒤 answer를 1 증가시키므로 같은 섬을 중복 계산하지 않습니다.

코드의 핵심

제출 코드는 directions에 상하좌우 네 방향을 두고, BFS에서 deque의 popleft()로 칸을 꺼내 인접한 미방문 0을 큐에 넣습니다. 큐에 넣는 순간 visited를 참으로 바꾸므로 같은 칸이 여러 번 큐에 들어가지 않습니다.

가장자리 순회는 왼쪽·오른쪽 열을 먼저, 위쪽·아래쪽 행을 다음에 확인합니다. 모서리는 두 번 검사할 수 있지만, 이미 visited인지 확인하므로 같은 연결 요소를 다시 탐색하지 않습니다. 내부 순회는 range(1,n-1)과 range(1,m-1)로 테두리를 제외합니다.

예제 2를 코드 순서대로 보면, 가장자리의 0들과 연결된 칸들이 먼저 방문 처리됩니다. 내부 범위에서 확인되는 (1,2)는 값이 0이고 미방문이므로 BFS(1,2)를 실행하고 answer를 1 증가시킵니다. 이후 내부에 남은 미방문 0이 없으므로 반환값은 1입니다.

제출 코드

from collections import deque

class Solution:
    def closedIsland(self, grid: list[list[int]]) -> int:
        n = len(grid)
        m = len(grid[0])

        visited = [[False] * m for i in range(n)]
        directions = [(0,1),(0,-1),(1,0),(-1,0)]
        def BFS(i,j):
            queue = deque()
            queue.append((i,j))
            visited[i][j] = True

            while queue:
                x,y = queue.popleft()
                for dx,dy in directions:
                    sx,sy = x+dx,y+dy
                    if 0<=sx<n and 0<=sy<m and grid[sx][sy] == 0 and not visited[sx][sy]:
                        queue.append((sx,sy))
                        visited[sx][sy] = True

        for i in range(n):
            if grid[i][0] == 0 and not visited[i][0]:
                BFS(i,0)
            if grid[i][m-1] == 0 and not visited[i][m-1]:
                BFS(i,m-1)
        for j in range(m):
            if grid[0][j] == 0 and not visited[0][j]:
                BFS(0,j)
            if grid[n-1][j] == 0 and not visited[n-1][j]:
                BFS(n-1,j)

        answer = 0
        for i in range(1,n-1):
            for j in range(1,m-1):
                if grid[i][j] == 0 and not visited[i][j]:
                    BFS(i,j)
                    answer += 1

        return answer

복잡도

n = len(grid), m = len(grid[0])이라 두면 각 칸은 방문 처리된 뒤 다시 BFS에 들어가지 않으므로 시간 복잡도는 O(nm)입니다. visited는 O(nm)의 보조 공간을 사용하고, 큐도 최악에는 한 연결 요소의 칸들을 담아 O(nm)까지 사용할 수 있습니다.

복습 포인트

가장자리에 닿는 섬은 열린 섬으로 제외됩니다. n < 3 또는 m < 3이면 내부 순회 범위가 비므로 반환값은 0입니다. 코드가 grid[0]을 참조하므로 입력은 비어 있지 않은 것으로 전제합니다.

출처

문제 원문