파이썬으로 물에 완전히 둘러싸인 섬 제거하기

문제 정의

이진 행렬(binary matrix)이 주어졌을 때, 1은 육지(land), 0은 물(water)을 나타냅니다. 여기서 '섬(island)'이란 상하좌우로 인접한 1들의 그룹을 의미하며, 이 그룹은 물 또는 행렬의 가장자리에 의해 둘러싸여 있습니다.

우리가 찾아야 할 대상은 물로 완전히 둘러싸인 섬, 즉 행렬의 가장자리와 맞닿아 있지 않은 섬입니다. 이런 섬을 모두 찾아내어 0으로 변경하는 것이 목표입니다. 단, 이웃 판정 시 대각선 방향은 제외하고 수평·수직 방향만 고려합니다.

예시로 이해하기

다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

1	0	0	0
0	1	1	0
0	1	1	0
0	1	1	0
0	0	0	1

그렇다면 출력은 다음과 같습니다.

1	0	0	0
0	0	0	0
0	0	0	0
0	0	0	0
0	0	0	1

행렬 중앙의 2×3 크기 섬은 사방이 물로 둘러싸여 있어 모두 0으로 변경되었습니다. 반면 좌측 상단 모서리의 1과 우측 하단 모서리의 1은 가장자리와 맞닿아 있으므로 그대로 유지됩니다.

해결 전략: 반대로 생각하기

물에 갇힌 섬을 직접 찾는 것보다 가장자리와 연결된 육지만 골라내는 방식이 훨씬 효율적입니다. 가장자리에 위치한 육지에서 출발해 연결된 모든 육지를 너비 우선 탐색(BFS)으로 방문하고, 결과 행렬 B에 기록합니다. 그러면 B에 기록되지 않은 육지가 바로 물에 완전히 둘러싸인 섬이 되어 자연스럽게 0으로 처리됩니다.

구체적인 알고리즘 단계는 다음과 같습니다.

row := 행렬 A의 행 개수
col := 행렬 A의 열 개수
B := A와 같은 크기의 행렬을 만들고 0으로 채움
seen := 방문 여부를 저장할 빈 집합(set)
행렬의 가장자리에 있는 모든 칸 (i, j)에 대해 반복:
- (i, j)가 이미 방문했거나 물(0)이면 건너뜀
- d := 시작점 (i, j)를 담은 덱(deque) 생성 후 BFS 시작
- d가 빌 때까지 반복:
  - d의 앞에서 칸 (x, y)를 꺼내고 B[x][y] := 1로 설정
  - (x, y)의 상하좌우 이웃 중 아직 방문하지 않은 육지를 d에 추가하고 seen에 기록
모든 탐색이 끝나면 B를 반환

파이썬 구현 코드

아래 예제를 통해 더 잘 이해해 보겠습니다.

from collections import deque
class Solution:
    def solve(self, A):
        row = len(A)
        col = len(A[0])
        B = [[0 for _ in range(col)] for _ in range(row)]
        seen = set()

        def nei(i, j):
            if i + 1 < row and A[i + 1][j]:
                yield (i + 1, j)
            if j + 1 < col and A[i][j + 1]:
                yield (i, j + 1)
            if i - 1 >= 0 and A[i - 1][j]:
                yield (i - 1, j)
            if j - 1 >= 0 and A[i][j - 1]:
                yield (i, j - 1)

        for i in range(row):
            for j in range(col):
                # 가장자리가 아니면 건너뜀
                if i not in (0, row - 1) and j not in (0, col - 1):
                    continue
                if (i, j) in seen:
                    continue
                if A[i][j] == 0:
                    continue
                d = deque([(i, j)])
                seen.add((i, j))
                while d:
                    x, y = d.popleft()
                    B[x][y] = 1
                    for x2, y2 in nei(x, y):
                        if (x2, y2) not in seen:
                            d.append((x2, y2))
                            seen.add((x2, y2))
        return B

ob = Solution()
matrix = [
    [1, 0, 0, 0],
    [0, 1, 1, 0],
    [0, 1, 1, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 1],
]
print(ob.solve(matrix))

실행 결과

입력

[
    [1, 0, 0, 0],
    [0, 1, 1, 0],
    [0, 1, 1, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 1],
]

출력

[
    [1, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 1]
]

핵심 포인트 정리

역발상: 갇힌 섬을 직접 찾는 대신, 가장자리에서 도달 가능한 육지만 남기는 방식으로 문제를 단순화했습니다.
BFS 활용: 덱(deque)을 사용한 너비 우선 탐색으로 가장자리 육지와 연결된 모든 땅을 효율적으로 방문합니다.
방문 처리: seen 집합으로 같은 칸을 중복 방문하지 않도록 하여 불필요한 연산을 방지합니다.

시간 및 공간 복잡도

모든 칸을 최대 한 번씩만 방문하므로 시간 복잡도는 O(row × col)입니다. 방문 여부를 저장하는 집합과 결과 행렬 B가 필요하므로 공간 복잡도 역시 O(row × col)입니다.

파이썬으로 물에 완전히 둘러싸인 섬 제거하기 – BFS 알고리즘 구현 가이드