0과 1로만 이루어진 이진 행렬(binary matrix)이 하나 주어졌다고 가정해 보겠습니다. 여기서 0은 빈 칸을, 1은 사람이 있는 칸을 의미합니다. 두 칸 사이의 거리는 x 좌표 차이와 y 좌표 차이 중 더 큰 값, 즉 체비셰프 거리(Chebyshev distance)로 정의됩니다. 만약 어떤 빈 칸이 존재하여 그 칸에서 행렬 안의 모든 사람까지의 거리와 행렬의 네 변(경계)까지의 거리가 모두 k 이상이라면, 이 행렬을 안전 인자(safety factor) k에 대해 안전하다고 말합니다. 우리가 구해야 하는 것은 바로 이 안전 인자 k의 최댓값입니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
이 경우 출력은 1입니다. 행렬의 가운데 칸에서 그리드 내 모든 사람까지의 거리가 최소 1 이상이기 때문입니다.
문제 해결 접근 방식
이 문제는 동적 계획법(DP)을 활용한 '가장 큰 빈 정사각형' 알고리즘으로 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
N := 행렬 A의 행(row) 개수
M := 행렬 A의 열(column) 개수
행렬의 모든 원소를 순회하며 A[i][j] ^= 1 연산으로 값을 반전시킵니다. 이렇게 하면 빈 칸이 1이 되어, 문제가 '1로만 이루어진 가장 큰 정사각형 찾기' 문제로 변환됩니다.
ans := 0 으로 초기화합니다.
다시 행렬 전체를 순회하면서, i와 j가 0이 아니고 A[i][j]가 1인 경우 다음을 수행합니다.
A[i][j] := 1 + min(A[i-1][j], A[i][j-1], A[i-1][j-1]) — 현재 칸을 오른쪽 아래 꼭짓점으로 하는 가장 큰 빈 정사각형의 한 변 길이를 계산합니다.
ans := max(ans, A[i][j]) 로 최댓값을 갱신합니다.
마지막으로 (ans + 1) // 2를 반환합니다. 가장 큰 빈 정사각형의 중심에 위치했을 때 얻을 수 있는 안전 거리가 곧 최댓값이 되기 때문입니다.
이 알고리즘의 시간 복잡도는 O(N×M)으로, 행렬을 두 번만 순회하면 되므로 매우 효율적입니다.
예제 구현
아래 파이썬 코드를 통해 실제 구현을 살펴보겠습니다.
class Solution:
def solve(self, A):
N = len(A)
M = len(A[0])
for i in range(N):
for j in range(M):
A[i][j] ^= 1
ans = 0
for i in range(N):
for j in range(M):
if i and j and A[i][j]:
A[i][j] = 1 + min(A[i - 1][j], A[i][j - 1], A[i - 1][j - 1])
ans = max(A[i][j], ans)
return (ans + 1) // 2
ob = Solution()
matrix = [
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 1, 0, 1, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0],
]
print(ob.solve(matrix))
입력
[ [0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 1, 0, 1, 0], [0, 1, 1, 1, 0], [0, 0, 0, 0, 0], ]
출력
1