2차원 이진 행렬(binary matrix)이 주어졌다고 가정해 보겠습니다. 여기서 1은 육지를, 0은 물을 나타냅니다. 섬(island)이란 물에 둘러싸인 인접한 1들의 그룹을 의미하며, 행렬의 가장자리 역시 모두 물로 둘러싸여 있다고 가정할 수 있습니다. 우리가 구해야 하는 것은 이 행렬에서 가장 큰 섬의 면적, 즉 연결된 육지 칸(cell)의 최대 개수입니다.
입력 예시
예를 들어 입력이 다음과 같다면,
| 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 |
첫 번째 줄의 육지 5칸과 세 번째·네 번째 줄에 걸쳐 연결된 육지들이 각각 하나의 섬을 이루며, 이 중 가장 큰 섬의 면적은 6입니다. 따라서 출력 결과는 다음과 같습니다.
6
문제 해결 접근 방식
이 문제는 DFS(깊이 우선 탐색)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 행렬을 순회하면서 값이 1인 칸을 발견하면, 그 지점에서 DFS를 시작해 상하좌우로 연결된 모든 육지를 탐색합니다.
- 탐색한 칸은 다시 방문하지 않도록 값을 0으로 바꿔줍니다(방문 처리).
- 탐색이 끝나면 방문한 칸의 총 개수, 즉 해당 섬의 면적을 구할 수 있습니다.
- 모든 섬의 면적 중 최댓값을 반환합니다.
알고리즘 단계
- dfs(matrix, r, c) 함수를 정의합니다.
- total 값을 1 증가시키고, 현재 위치 matrix[r][c]를 0으로 변경하여 방문 처리합니다.
- 위쪽 칸(r - 1, c)이 행렬 범위 내에 있고 값이 1이면 dfs(matrix, r - 1, c)를 재귀 호출합니다.
- 왼쪽 칸(r, c - 1)이 행렬 범위 내에 있고 값이 1이면 dfs(matrix, r, c - 1)를 재귀 호출합니다.
- 아래쪽 칸(r + 1, c)이 행렬 범위 내에 있고 값이 1이면 dfs(matrix, r + 1, c)를 재귀 호출합니다.
- 오른쪽 칸(r, c + 1)이 행렬 범위 내에 있고 값이 1이면 dfs(matrix, r, c + 1)를 재귀 호출합니다.
메인 메서드에서는 다음 과정을 수행합니다.
- r_len := 행렬의 행(row) 개수, c_len := 행렬의 열(column) 개수로 설정합니다.
- max_island := 0으로 초기화합니다.
- 모든 좌표 (r, c)를 순회하면서 matrix[r][c]가 1이면 total을 0으로 초기화한 뒤 dfs(matrix, r, c)를 호출하고, max_island를 max_island와 total 중 더 큰 값으로 갱신합니다.
- 순회가 끝나면 max_island를 반환합니다.
파이썬 구현 코드
아래는 위 알고리즘을 파이썬으로 구현한 전체 코드입니다.
class Solution:
def solve(self, matrix):
self.r_len = len(matrix)
self.c_len = len(matrix[0])
max_island = 0
for r in range(self.r_len):
for c in range(self.c_len):
if matrix[r][c] == 1:
self.total = 0
self.dfs(matrix, r, c)
max_island = max(max_island, self.total)
return max_island
def dfs(self, matrix, r, c):
self.total += 1
matrix[r][c] = 0
if r - 1 >= 0 and matrix[r - 1][c] == 1:
self.dfs(matrix, r - 1, c)
if c - 1 >= 0 and matrix[r][c - 1] == 1:
self.dfs(matrix, r, c - 1)
if r + 1 < self.r_len and matrix[r + 1][c] == 1:
self.dfs(matrix, r + 1, c)
if c + 1 < self.c_len and matrix[r][c + 1] == 1:
self.dfs(matrix, r, c + 1)
ob = Solution()
matrix = [
[0, 0, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 0, 0],
[0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 1, 0]
]
print(ob.solve(matrix))
입력
matrix = [
[0, 0, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 0, 0],
[0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 1, 0]
]
출력
6
시간 복잡도와 공간 복잡도
이 알고리즘의 시간 복잡도는 O(R × C)입니다. R은 행의 개수, C는 열의 개수로, 각 칸은 최대 한 번만 방문하기 때문입니다. 공간 복잡도 역시 재귀 호출 스택 깊이가 최악의 경우 O(R × C)까지 늘어날 수 있습니다. 만약 행렬의 크기가 매우 커서 재귀 깊이 제한에 걸릴 우려가 있다면, sys.setrecursionlimit()으로 제한을 조정하거나 BFS 및 명시적 스택을 사용하는 반복(iterative) 방식으로 대체하는 것이 좋습니다.