0과 1로 이루어진 이진 행렬(binary matrix)이 있다고 가정해 보겠습니다. 우리가 해야 할 일은 이 행렬 안에 섬이 몇 개 있는지 세는 것입니다. 여기서 1은 육지를, 0은 물을 의미합니다. 즉, 섬이란 서로 인접한 1들의 그룹으로, 그 둘레가 모두 물(0)로 둘러싸여 있는 영역을 말합니다.
단, 이 문제에서 인접(adjacent)은 수평 또는 수직 방향만 고려하며, 대각선 방향은 인접으로 취급하지 않습니다.
예를 들어 입력 행렬이 다음과 같다면,
| 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 |
출력 결과는 4가 됩니다.
문제 해결 접근 방법
이 문제는 전형적인 그래프 탐색 문제로, DFS(깊이 우선 탐색)를 활용해 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 행렬을 처음부터 끝까지 순회하면서 값이 1인 칸을 발견하면, 새로운 섬을 하나 발견한 것이므로 섬의 개수를 1 증가시킵니다.
- 그리고 그 지점에서 출발해 상하좌우로 연결된 모든 1을 재귀적으로 탐색(explore)하면서 0으로 바꿔 버립니다. 이렇게 하면 이미 확인한 섬을 중복해서 세는 실수를 방지할 수 있습니다.
구체적인 절차는 다음과 같습니다.
explore(row, col, matrix)함수를 정의합니다.- row와 col이 행렬 범위를 벗어나거나
matrix[row][col]이 0이면 그대로 반환(return)합니다. matrix[row][col]을 0으로 변경하여 방문 처리를 합니다.- 상하좌우 네 방향에 대해 각각
explore()를 재귀 호출합니다. - 메인 메서드에서는 다음을 수행합니다.
- 행렬이 비어 있으면 0을 반환합니다.
- islands 변수를 0으로 초기화합니다.
- 모든 행과 열을 순회하면서
matrix[row][col] == 1인 경우 islands를 1 증가시키고explore(row, col)을 호출합니다.
- 순회가 끝나면 islands 값을 반환합니다.
예제 코드
class Solution:
def explore(self, row, col, matrix):
if (row < 0 or col < 0 or row > len(matrix) - 1
or col > len(matrix[0]) - 1
or matrix[row][col] == 0):
return
matrix[row][col] = 0
self.explore(row + 1, col, matrix)
self.explore(row - 1, col, matrix)
self.explore(row, col + 1, matrix)
self.explore(row, col - 1, matrix)
def solve(self, matrix):
if not matrix:
return 0
islands = 0
for row in range(len(matrix)):
for col in range(len(matrix[0])):
if matrix[row][col] == 1:
islands += 1
self.explore(row, col, matrix)
return islands
ob = Solution()
matrix = [
[1, 0, 1, 0, 0],
[0, 0, 1, 0, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 0, 0],
[1, 1, 0, 1, 1],
[1, 1, 1, 0, 1]
]
print(ob.solve(matrix))
입력
[
[1, 0, 1, 0, 0],
[0, 0, 1, 0, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 0, 0],
[1, 1, 0, 1, 1],
[1, 1, 1, 0, 1]
]
출력
4
시간 및 공간 복잡도
모든 칸을 한 번씩만 방문하므로 시간 복잡도는 O(M×N)입니다. 여기서 M은 행의 개수, N은 열의 개수입니다. 공간 복잡도는 재귀 호출 스택의 깊이에 의해 결정되며, 최악의 경우(전체가 육지인 경우) O(M×N)까지 증가할 수 있습니다.