문제 소개
0과 1로만 구성된 이진 행렬(binary matrix)이 주어졌을 때, 행렬의 모든 칸에 대해 그 칸에서 가장 가까운 1이 위치한 칸까지의 최소 거리를 구하는 것이 이번 글의 목표입니다.
여기서 말하는 거리는 맨해튼 거리(Manhattan Distance)를 의미합니다. 현재 칸의 좌표를 (i, j), 목표 칸의 좌표를 (k, l)이라 할 때 거리는 다음과 같이 정의됩니다.
distance = |i - k| + |j - l|
구체적인 예제를 통해 살펴보겠습니다.
입력
0 0 1
1 1 0
0 0 0
출력
1 1 0
0 0 1
1 1 2
위 결과에서 확인할 수 있듯이, 값이 1인 칸은 자기 자신이 곧 가장 가까운 1이므로 거리가 0이 됩니다. 반면 값이 0인 칸은 인접한 1까지의 거리가 계산됩니다. 예를 들어 마지막 칸 (2, 2)는 가장 가까운 1인 (1, 1)까지 두 칸 떨어져 있으므로 거리가 2가 됩니다.
알고리즘
가장 직관적인 접근 방법은 브루트 포스(Brute Force) 방식으로, 각 칸마다 행렬 전체를 탐색하며 가장 가까운 1을 찾는 것입니다. 단계별로 정리하면 다음과 같습니다.
주어진 크기의 행렬을 초기화합니다.
거리를 저장할 같은 크기의 또 다른 행렬을 초기화합니다.
행렬 전체를 순회하면서 다음을 수행합니다.
현재 칸의 값이 1이면, 1에서 1까지의 거리는 0이므로 해당 칸의 거리를 0으로 설정합니다.
현재 칸의 값이 0이면:
행렬 전체를 다시 한 번 순회합니다.
탐색 중 만난 칸의 값이 1이면, 현재 칸으로부터의 거리를 계산합니다.
계산된 거리가 기존 최소 거리보다 작으면 값을 갱신합니다.
모든 순회가 끝나면 거리 행렬을 출력합니다.
C++ 구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> findNearest1Distance(vector<vector<int>>& matrix) {
int rows = matrix.size();
if (rows == 0) {
return matrix;
}
int cols = matrix[0].size();
vector<vector<int>> distance(rows, vector<int>(cols, INT_MAX));
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 1) {
distance[i][j] = 0;
} else if (matrix[i][j] == 0) {
for (int k = 0; k < rows; k++) {
for (int l = 0; l < cols; l++) {
if (matrix[k][l] == 1) {
distance[i][j] = min(distance[i][j], abs(k - i) + abs(l - j));
}
}
}
}
}
}
return distance;
}
int main() {
vector<vector<int>> matrix{
{0, 0, 1},
{1, 1, 0},
{0, 0, 0}
};
vector<vector<int>> result = findNearest1Distance(matrix);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cout << result[i][j] << " ";
}
cout << endl;
}
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
1 1 0
0 0 1
1 1 2
복잡도 분석 및 개선 방향
위 브루트 포스 방식은 각 칸마다 행렬 전체를 다시 탐색하므로 시간 복잡도가 O((m×n)²)입니다. 여기서 m과 n은 각각 행렬의 행과 열의 개수입니다. 공간 복잡도는 거리 행렬 저장을 위해 O(m×n)입니다.
행렬의 크기가 커지면 이 방식은 비효율적일 수 있습니다. 이 경우 멀티소스 BFS(너비 우선 탐색)를 활용하면 시간 복잡도를 O(m×n)까지 줄일 수 있습니다. 모든 1인 칸을 큐에 동시에 넣고 시작한 뒤 상하좌우로 확장해 나가면, 각 칸의 최단 거리를 한 번의 탐색만으로 구할 수 있습니다.