0과 1로 이루어진 이진 행렬(binary matrix)이 있다고 가정해 보겠습니다. 여기서 1은 육지를, 0은 물을 나타냅니다. 섬이란 물에 둘러싸여 있는 1들의 집합을 의미하는데, 이번 문제에서 구해야 할 것은 바로 완전히 물에 둘러싸인 섬, 즉 행렬의 가장자리와 맞닿아 있지 않은 섬의 개수입니다.
예를 들어 입력이 다음과 같다면,
출력은 2가 됩니다. 전체 섬은 세 개지만, 그중 두 개만 사방이 물로 완전히 둘러싸여 있기 때문입니다.
문제 해결 접근 방식: DFS(깊이 우선 탐색)
이 문제는 DFS(깊이 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 섬을 탐색하면서 그 섬이 행렬의 경계 밖으로 뻗어 나가는지 확인하는 것입니다.
dfs() 함수의 동작 원리
- dfs(i, j) 함수를 정의합니다. 현재 위치의 좌표 i, j를 인자로 받습니다.
- i 또는 j가 행렬 범위를 벗어나면
False를 반환합니다. 즉, 해당 섬은 경계와 연결되어 있어 '완전히 둘러싸인 섬'이 아닙니다. - matrix[i][j]가 0(물)이라면
True를 반환합니다. 물은 섬의 확장을 막으므로 아직까지는 둘러싸여 있다는 의미입니다. - 현재 위치를 방문 처리하기 위해 matrix[i][j]를 0으로 변경합니다.
- 상하좌우 네 방향을 재귀적으로 탐색한 결과(a, b, c, d)를 모두 AND 연산하여 반환합니다.
메인 로직
- R은 행렬의 행 개수, C는 열 개수로 설정합니다.
- 정답을 저장할 변수 ans를 0으로 초기화합니다.
- 모든 칸을 순회하면서 값이 1인 지점을 발견하면 dfs(i, j)를 호출하고, 결과가 True라면 ans를 1 증가시킵니다.
- 순회가 끝나면 ans를 반환합니다.
구현 예제
class Solution:
def solve(self, matrix):
def dfs(i, j):
if i < 0 or j < 0 or i >= R or j >= C:
return False
if matrix[i][j] == 0:
return True
matrix[i][j] = 0
a = dfs(i + 1, j)
b = dfs(i - 1, j)
c = dfs(i, j + 1)
d = dfs(i, j - 1)
return a and b and c and d
R, C = len(matrix), len(matrix[0])
ans = 0
for i in range(R):
for j in range(C):
if matrix[i][j] == 1:
if dfs(i, j):
ans += 1
return ans
ob = Solution()
matrix = [
[1, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 1, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0]
]
print(ob.solve(matrix))입력
matrix = [ [1, 0, 0, 0, 0], [0, 0, 0, 1, 0], [0, 1, 0, 0, 0], [0, 1, 0, 0, 0], [0, 1, 1, 1, 0], [0, 0, 0, 0, 0] ]
출력
2
정리
이 알고리즘은 행렬의 모든 칸을 한 번씩 방문하므로 시간 복잡도는 O(R×C)입니다. 방문한 육지를 0으로 바꾸어 재방문을 방지하기 때문에 별도의 visited 배열 없이도 중복 탐색을 피할 수 있다는 점이 특징입니다. 이처럼 DFS를 응용하면 섬의 개수 세기, 섬의 크기 계산 등 다양한 격자(grid) 기반 그래프 문제를 손쉽게 해결할 수 있습니다.