JavaScript로 이진 행렬에서 가장 가까운 0까지의 거리 구하기

문제 소개

이진 행렬(Binary Matrix)이란 0 또는 1만 포함하는 배열의 배열을 의미합니다. 이번 글에서는 이진 행렬을 유일한 인자로 받아, 각 위치에서 가장 가까운 0까지의 거리를 계산한 새로운 행렬을 반환하는 JavaScript 함수를 작성해 보겠습니다.

결과 행렬은 원본 행렬과 동일한 행과 열의 개수를 가져야 하며, 각 요소에는 원본 행렬에서 해당 위치가 0으로부터 떨어져 있는 최단 거리가 저장됩니다.

여기서 중요한 조건은 두 가지입니다. 첫째, 거리를 계산할 때 상하좌우(가로·세로) 방향으로만 이동할 수 있으며 대각선 이동은 허용되지 않습니다. 둘째, 입력되는 행렬에는 최소한 하나의 0이 반드시 존재한다고 보장됩니다.

예시

예를 들어 다음과 같은 입력 행렬이 있다고 가정해 보겠습니다.

const arr = [
    [0, 0, 0],
    [0, 1, 0],
    [1, 1, 1]
];

이 경우 기대되는 출력 행렬은 다음과 같습니다.

const output = [
    [0, 0, 0],
    [0, 1, 0],
    [1, 2, 1]
];

위 출력에서 확인할 수 있듯이, 값이 1인 요소들은 인접한 0까지의 거리에 따라 1 또는 2로 계산됩니다.

알고리즘 접근 방식: BFS(너비 우선 탐색)

이 문제는 BFS(Breadth-First Search) 방식으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 0이 있는 모든 좌표를 시작점으로 삼아, 각 단계마다 인접한 칸으로 거리 값을 하나씩 확산시키는 것입니다.

행렬을 순회하면서 값이 0인 위치는 결과에 0을 기록하고 해당 좌표를 큐에 추가합니다.
값이 1인 위치는 일단 매우 큰 값(Number.MAX_SAFE_INTEGER)으로 초기화하여 아직 거리가 계산되지 않았음을 표시합니다.
큐에서 좌표를 하나씩 꺼내 상하좌우 인접 칸을 확인하고, 경계를 벗어나지 않으면서 더 작은 거리 값으로 갱신할 수 있다면 '현재 거리 + 1'로 업데이트한 뒤 그 좌표를 큐에 추가합니다.
큐가 빌 때까지 이 과정을 반복하면 모든 칸에 대해 가장 가까운 0까지의 거리가 완성됩니다.

구현 코드

이를 JavaScript로 구현한 코드는 다음과 같습니다.

const arr = [
    [0, 0, 0],
    [0, 1, 0],
    [1, 1, 1],
];
const findNearestDistance = (arr = []) => {
    let array = [];
    let res = arr.map((el, ind) => el.map((subEl, subInd) => {
        if (subEl === 0) {
            array.push([ind, subInd])
            return 0
        };
        return Number.MAX_SAFE_INTEGER;
    }));
    const updateAdjacent = (ind, subInd, min, array = []) => {
        if (ind < 0 || subInd < 0 || ind == arr.length || subInd == arr[0].length){
            return;
        };
        if (res[ind][subInd] < min + 2) return
            res[ind][subInd] = min + 1
            array.push([ind, subInd])
    };
    while (array.length) {
        let next = []
        for (let [ind, subInd] of array) {
            updateAdjacent(ind, subInd + 1, res[ind][subInd], next)
            updateAdjacent(ind, subInd - 1, res[ind][subInd], next)
            updateAdjacent(ind + 1, subInd, res[ind][subInd], next)
            updateAdjacent(ind - 1, subInd, res[ind][subInd], next)
        };
        array = next;
    }
    return res;
};
console.log(findNearestDistance(arr));

실행 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

[ [ 0, 0, 0 ], [ 0, 1, 0 ], [ 1, 2, 1 ] ]

마무리

이처럼 BFS를 활용하면 이진 행렬에서 각 지점의 가장 가까운 0까지의 거리를 효율적으로 계산할 수 있습니다. 행렬의 모든 칸을 최대 한 번씩만 방문하므로 시간 복잡도는 O(m×n)으로, 행과 열의 개수에 비례하는 선형 시간 안에 문제를 해결할 수 있다는 점이 이 알고리즘의 큰 장점입니다.