두 개의 이진 행렬 mat1과 mat2가 주어졌다고 가정해 봅시다. 여기서 1은 육지를, 0은 물을 의미하며, 물로 둘러싸인 1(육지)들의 집합을 '섬'이라고 정의합니다. 우리가 구해야 할 것은 mat1과 mat2 양쪽에 정확히 같은 좌표에 걸쳐 존재하는 섬의 개수입니다.
문제 예시
예를 들어 입력이 다음과 같다고 해보겠습니다.
mat1:
| 1 | 0 | 1 |
| 1 | 0 | 0 |
| 1 | 0 | 0 |
mat2:
| 1 | 0 | 1 |
| 1 | 0 | 0 |
| 1 | 0 | 1 |
이 경우 출력은 2가 됩니다. 겹치는 섬들은 아래와 같이 표시되며, 왼쪽의 L자 형태 섬과 오른쪽 상단의 단일 셀 섬, 총 두 개가 두 행렬에서 동일한 위치에 존재하기 때문입니다.
| 1 | 0 | 1 |
| 1 | 0 | 0 |
| 1 | 0 | 1 |
풀이 접근 방법
이 문제는 DFS(깊이 우선 탐색) 기반의 마킹 기법으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 두 행렬에서 값이 서로 다른 칸이 있다면, 그 칸은 어떤 경우에도 '겹치는 섬'에 포함될 수 없습니다. 따라서 해당 칸을 시작점으로 양쪽 행렬에 연결된 육지를 모두 지워버립니다.
- 그 후 남아 있는 육지 덩어리(섬)의 개수를 세면, 그것이 바로 두 행렬에 공통으로 존재하는 섬의 개수입니다.
알고리즘 단계
- r := mat1의 행 개수
- c := mat1의 열 개수
- last_row := r - 1, last_col := c - 1
- 함수 mark(i, j)를 정의합니다:
- mat1[i][j]와 mat2[i][j]를 모두 0으로 설정 (방문 처리)
- 상하좌우 인접 칸 중 하나라도 mat1 또는 mat2에서 육지(1)라면 재귀적으로 mark() 호출하여 연결된 영역을 모두 제거
- 메인 로직:
- 모든 칸을 순회하며 mat1[i][j] != mat2[i][j]인 칸을 발견하면 mark(i, j) 호출 — 불일치 영역 제거
- islands := 0으로 초기화한 뒤, 다시 전체를 순회하며 mat1[i][j]가 1인 칸을 만나면 islands를 1 증가시키고 mark(i, j)로 해당 섬 전체를 제거
- 최종적으로 islands를 반환합니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
def solve(mat1, mat2):
r = len(mat1)
c = len(mat1[0])
last_row = r - 1
last_col = c - 1
def mark(i, j):
mat1[i][j] = mat2[i][j] = 0
if i and (mat1[i - 1][j] or mat2[i - 1][j]):
mark(i - 1, j)
if j and (mat1[i][j - 1] or mat2[i][j - 1]):
mark(i, j - 1)
if j < last_col and (mat1[i][j + 1] or mat2[i][j + 1]):
mark(i, j + 1)
if i < last_row and (mat1[i + 1][j] or mat2[i + 1][j]):
mark(i + 1, j)
for i in range(r):
for j in range(c):
if mat1[i][j] != mat2[i][j]:
mark(i, j)
islands = 0
for i in range(r):
for j in range(c):
if mat1[i][j]:
islands += 1
mark(i, j)
return islands
mat1 = [
[1, 0, 1],
[1, 0, 0],
[1, 0, 1]
]
mat2 = [
[1, 0, 1],
[1, 0, 0],
[1, 0, 0]
]
print(solve(mat1, mat2))입력
[ [1, 0, 1], [1, 0, 0], [1, 0, 1] ] [ [1, 0, 1], [1, 0, 0], [1, 0, 0] ]
출력
2
복잡도 분석
시간 복잡도는 각 칸을 최대 몇 번 방문하느냐에 따라 O(r × c)이며, 공간 복잡도는 재귀 호출 스택 깊이에 의해 최악의 경우 O(r × c)입니다. 추가적인 방문 배열 없이 입력 행렬 자체를 수정하여 마킹하기 때문에 메모리 사용이 효율적입니다.