문제 개요
0과 1로 구성된 이진 행렬(binary matrix)이 주어졌다고 가정해 봅시다. 여기서 1은 육지를, 0은 물을 의미합니다. 임의의 육지 칸에서는 상하좌우 네 방향으로만 이동할 수 있으며, 대각선 이동은 허용되지 않습니다. 이때 행렬의 바깥으로 빠져나갈 수 없는 육지 칸이 몇 개인지 구하는 프로그램을 작성하는 것이 목표입니다.
예시
다음과 같은 행렬이 입력으로 주어진다고 해보겠습니다.
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 |
이 경우 정답은 4입니다. 행렬 중앙에 위치한 4개의 육지 칸은 어떤 경로로도 행렬 밖으로 걸어 나갈 수 없기 때문입니다.
풀이 접근 방식
핵심 아이디어는 행렬의 가장자리에 있는 모든 육지 칸에서 출발하여 연결된 육지를 모두 제거(방문 처리)하는 것입니다. 이 과정이 끝난 뒤 행렬에 남아 있는 1의 개수가 곧 탈출할 수 없는 육지 칸의 개수가 됩니다. 너비 우선 탐색(BFS) 방식으로 구현하면 다음 단계를 따릅니다.
- 1단계: 행렬의 테두리(첫 번째 행, 마지막 행, 첫 번째 열, 마지막 열)에 있는 모든 육지 칸의 좌표 (i, j)를 큐(q)에 담습니다.
- 2단계: 인덱스 변수 idx를 0으로 초기화합니다.
- 3단계: 큐에 담긴 모든 좌표 (x, y)에 대해 해당 칸의 값을 0으로 변경합니다.
- 4단계: idx가 큐의 길이보다 작은 동안 다음을 반복합니다.
- 큐에서 (x, y)를 꺼내고, 네 방향 [(-1, 0), (0, -1), (0, 1), (1, 0)]을 차례로 검사합니다.
- 인접 좌표 (nx, ny)가 행렬 범위 안에 있고 그 값이 1이라면, 해당 칸을 0으로 바꾸고 큐의 끝에 추가합니다.
- 5단계: 탐색이 종료되면 행렬의 모든 요소의 합을 반환합니다. 이 값이 곧 정답입니다.
파이썬 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
def solve(matrix):
q = [(i, j) for i in range(len(matrix)) for j in range(len(matrix[i])) if matrix[i][j] and (i == 0 or i == len(matrix) - 1 or j == 0 or j == len(matrix[i]) - 1)]
idx = 0
for x, y in q:
matrix[x][y] = 0
while idx < len(q):
x, y = q[idx]
for dx, dy in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
nx, ny = x + dx, y + dy
if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[nx]) and matrix[nx][ny]:
matrix[nx][ny] = 0
q.append((nx, ny))
idx += 1
return sum(sum(row) for row in matrix)
matrix = [
[0, 0, 0, 1],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 1]
]
print(solve(matrix))
입력
[
[0, 0, 0, 1],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 1]
]
출력
4
마무리 및 복잡도 분석
이 문제는 전형적인 플러드 필(Flood Fill) 유형의 알고리즘 문제입니다. 행렬의 모든 칸을 최대 한 번씩만 방문하므로 시간 복잡도는 O(rows × cols)이며, 공간 복잡도 역시 O(rows × cols)입니다. 재귀 호출을 사용하는 DFS 대신 큐 기반의 BFS를 활용하면 행렬이 아무리 커져도 스택 오버플로우 걱정 없이 안정적으로 처리할 수 있다는 장점이 있습니다.