파이썬으로 물 칸 하나를 육지로 바꿔 만들 수 있는 가장 큰 섬 찾기

문제 소개

1은 육지를, 0은 물을 나타내는 이진 행렬(binary matrix)이 주어집니다. 여기서 섬(island)이란 물에 둘러싸여 있는 1들의 집합을 의미합니다. 우리가 구해야 할 것은 가장 큰 섬의 크기이며, 단 한 번 물 칸 하나를 육지 칸으로 변경할 수 있습니다.

예를 들어 입력 행렬이 다음과 같다고 해보겠습니다.

이 경우 정답은 7입니다. 두 번째 행의 첫 번째 칸(물)을 육지로 바꾸면 왼쪽 위의 작은 섬과 아래쪽의 큰 섬이 하나로 연결되기 때문입니다. 변경 후의 행렬은 다음과 같습니다.

풀이 접근 방식

이 문제는 플러드 필(Flood Fill) 기법과 해시맵을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 먼저 각 섬에 고유한 ID를 부여하면서 DFS(깊이 우선 탐색)로 모든 섬의 크기를 계산합니다.
• 그다음 모든 물 칸을 하나씩 확인하며, 해당 칸을 육지로 바꿨을 때 인접한 서로 다른 섬들이 하나로 합쳐졌을 때의 전체 크기를 계산합니다.
• 중복 계산을 피하기 위해 인접한 섬의 ID를 집합(set)에 저장합니다.

알고리즘 단계

1. R := 행렬의 행 개수, C := 행렬의 열 개수로 설정합니다.
2. mass := 각 섬 ID별 크기를 저장하는 새로운 맵을 생성합니다.
3. id := 555 (섬을 구분하기 위한 고유 ID의 시작 값)
4. floodfill(r, c, id) 함수를 정의합니다. r과 c가 행렬 범위 안에 있고 mat[r][c]가 1이라면:
   • mat[r][c] := id로 표시하고, mass[id] 값을 1 증가시킵니다.
   • 상하좌우 네 방향 (r+1, c), (r-1, c), (r, c+1), (r, c-1)에 대해 floodfill(r2, c2, id)를 재귀 호출합니다.
5. 메인 흐름에서는 행렬의 모든 칸을 순회하며 값이 1인 칸을 만날 때마다 id를 1 증가시키고, mass[id] := 0으로 초기화한 뒤 floodfill(r, c, id)를 호출해 해당 섬 전체를 표시하고 크기를 기록합니다.
6. ans := mass의 모든 값과 1 중 최댓값으로 설정합니다. (섬이 하나도 없는 경우를 대비한 초기값입니다.)
7. 모든 물 칸(mat[r][c] == 0)에 대해:
   • island_set := 새로운 집합을 생성합니다.
   • 상하좌우 이웃 칸 중 행렬 범위 안에 있고 육지인 칸의 섬 ID를 island_set에 추가합니다.
   • ans := max(ans, 1 + island_set에 속한 각 섬의 mass 합계)로 갱신합니다.
8. ans를 반환합니다.

파이썬 구현 예제

class Solution:
    def solve(self, mat):
        R, C = len(mat), len(mat[0])
        mass = {}
        id = 555

        def floodfill(r, c, id):
            nonlocal R, C, mat, mass
            if 0 <= r < R and 0 <= c < C and mat[r][c] == 1:
                mat[r][c] = id
                mass[id] += 1
                for r2, c2 in [(r + 1, c), (r - 1, c),
                               (r, c + 1), (r, c - 1)]:
                    floodfill(r2, c2, id)

        for r in range(R):
            for c in range(C):
                if mat[r][c] == 1:
                    id += 1
                    mass[id] = 0
                    floodfill(r, c, id)

        ans = max(list(mass.values()) + [1])

        for r in range(R):
            for c in range(C):
                if mat[r][c] != 0:
                    continue
                island_set = set()
                for r2, c2 in [(r + 1, c), (r - 1, c),
                               (r, c + 1), (r, c - 1)]:
                    if 0 <= r2 < R and 0 <= c2 < C and mat[r2][c2]:
                        island_set.add(mat[r2][c2])
                ans = max(ans, 1 + sum(mass[i] for i in island_set))
        return ans

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

입력

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

출력

7

복잡도 분석

행렬의 모든 칸을 상수 번씩만 방문하므로 시간 복잡도는 O(R × C)입니다. 재귀 호출 스택과 섬 정보를 저장하는 맵 때문에 공간 복잡도 역시 O(R × C)입니다.