문제 개요
2차원 이진 매트릭스가 주어졌다고 가정해 봅시다. 여기서 1은 살아있는 세포(live cell)를, 0은 죽은 세포(dead cell)를 의미합니다. 각 세포의 이웃(neighbors)은 해당 세포를 둘러싼 가로, 세로, 대각선 방향의 인접한 8개 칸을 말합니다.
우리는 다음과 같은 규칙에 따라 매트릭스의 다음 상태(next state)를 계산해야 합니다.
- 살아있는 세포의 경우, 살아있는 이웃이 2개 또는 3개라면 그대로 생존합니다.
- 죽어있는 세포의 경우, 살아있는 이웃이 정확히 3개라면 새롭게 태어나 살아있는 세포가 됩니다.
- 그 외의 모든 세포는 죽게 됩니다.
이 규칙은 수학자 존 컨웨이(John Conway)가 고안한 유명한 '라이프 게임(Game of Life)' 시뮬레이션의 핵심 로직과 동일합니다.
입력 및 출력 예시
예를 들어, 입력이 다음과 같다면:
| 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 |
출력 결과는 아래와 같습니다:
| 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 |
마지막 열의 두 세포(1, 1)가 살아있는 이웃 부족으로 소멸된 것을 확인할 수 있습니다.
알고리즘 접근 방법
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- 매트릭스의 행 크기를
n, 열 크기를m으로 설정합니다. - n × m 크기의 결과 매트릭스
res를 생성하고 모든 값을 0으로 초기화합니다. - 모든 좌표
(i, j)를 순회하며 각 세포의 살아있는 이웃 개수s를 계산합니다. 이때 현재 위치를 포함한 3×3 범위를 확인하되, 매트릭스 경계를 벗어나는 좌표는 제외합니다. - 현재 세포가 죽어 있는 경우(0): 이웃 중 살아있는 세포가 정확히 3개일 때만
res[i][j]를 1로 설정합니다. 참고로 자기 자신의 값이 0이므로, 3×3 범위의 합계에서 자기 자신을 빼지 않아도 됩니다. - 현재 세포가 살아있는 경우(1): 3×3 범위의 합계
s에는 자기 자신(값 1)이 포함됩니다. 따라서 생존 조건인 '살아있는 이웃 2~3개'는s == 3(자신 + 이웃 2) 또는s == 4(자신 + 이웃 3)일 때 성립합니다. 이 조건을 만족하면res[i][j]를 1로 설정합니다. - 모든 순회가 끝나면 결과 매트릭스
res를 반환합니다.
파이썬 구현 코드
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다:
class Solution:
def solve(self, matrix):
n, m = len(matrix), len(matrix[0])
res = [[0 for j in range(m)] for i in range(n)]
for i in range(n):
for j in range(m):
s = 0
if matrix[i][j] == 0:
for k in range(i - 1, i + 2):
for h in range(j - 1, j + 2):
if 0 <= k < n and 0 <= h < m:
s += matrix[k][h]
res[i][j] = [0, 1][s == 3]
else:
for k in range(i - 1, i + 2):
for h in range(j - 1, j + 2):
if 0 <= k < n and 0 <= h < m:
s += matrix[k][h]
if s in [3, 4]:
res[i][j] = 1
return res
ob = Solution()
matrix = [
[1, 1, 0, 0],
[0, 1, 0, 0],
[0, 1, 0, 1],
[1, 1, 0, 1]
]
print(ob.solve(matrix))
실행 결과
입력
[[1, 1, 0, 0],
[0, 1, 0, 0],
[0, 1, 0, 1],
[1, 1, 0, 1] ]
출력
[[1, 1, 0, 0],
[0, 1, 0, 0],
[0, 1, 0, 0],
[1, 1, 0, 0]]
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 O(n × m)입니다. 매트릭스의 모든 칸을 한 번씩 방문하며, 각 칸에서 최대 9개의 인접 칸(3×3 범위)만 확인하기 때문입니다. 공간 복잡도 역시 결과 매트릭스 저장을 위해 O(n × m)이 필요합니다.
핵심 포인트 정리
- 살아있는 세포의 생존 판정 시 자기 자신의 값이 합계에 포함되므로 조건을
s in [3, 4]로 처리하는 것이 핵심입니다. [0, 1][s == 3]표현식은 파이썬에서 불리언 값(True/False)을 인덱스로 활용하는 우아한 트릭으로, 조건이 참이면 1, 거짓이면 0을 반환합니다.- 경계 검사(
0 <= k < n and 0 <= h < m)를 통해 매트릭스 밖의 좌표 접근 오류(IndexError)를 방지합니다.