01 Matrix (BFS)

LeetCode의 Queue, Stack 튜토리얼의 마지막 섹션의 5번째 문제인 01 Matrix다.

Explore - LeetCode

문제는 다음과 같다.

• 0과 1로 이루어진 2차원 배열이 주어진다.

• 인접한 두 셀의 거리는 1이다.

• 각 셀은 상하좌우로만 인접하고 있다.

• 각 셀에서 가장 가까운 0셀까지의 거리를 2차원 배열로 반환하라.

문제에서 주어진 예시는 다음과 같다.

Input: [[0,0,0], [0,1,0], [0,0,0]] Output: [[0,0,0], [0,1,0], [0,0,0]]
Input: [[0,0,0], [0,1,0], [1,1,1]] Output: [[0,0,0], [0,1,0], [1,2,1]]

이를 그림으로 나타내 보면 다음과 같다.

먼저 모든 0셀은 자기 자신이 0 셀이기 때문에 거리는 0이다. 하지만 1셀에서는 0셀까지의 거리를 재야 하기 때문에 주변을 탐색해서 0셀을 찾아 그 거리를 저장해야 한다. 첫 번째 예제(위의 행렬)에서는 행렬의 (1, 1)에 있는 1셀에서 0셀까지의 거리는 바로 옆이나 위아래로 한 셀만 이동하면 되기 때문에 1이다. 이를 모든 1셀에 대해 수행하여 주어진 배열과 동일한 구조의 새로운 배열에 거리 값을 저장, 반환하는 것이 이번 문제의 목적이다.

 

보자마자 생각난 방법은 DFS, BFS인데 풀이 초반에는 DFS로 시도했었다. 하지만 DFS의 가장 중요한 특징인 "찾은 경로가 항상 최단 경로는 아니다"라는 점 때문에 제대로 된 답을 얻을 수 없었다. 0셀까지 최단 거리를 찾기 위해 현재 셀을 트리의 상위 노드로 해서 상하좌우 4방향의 이웃 셀들을 자식 노드로 뻗어가며 0셀을 찾을 때까지 진행, 반환한 거리 값을 비교해서 가장 작은 거리 값을 찾는 방법으로 구현하였는데 이는 중간부터 테스트 케이스를 통과하지 못했기 때문에 구현 또는 알고리즘 자체에 문제가 있던 것 같다.

 

그래서 풀이를 본 결과 이 문제는 BFS를 이용하여 풀 수 있는 문제였다. 어느 댓글에서도 그랬지만 closest, 즉 가장 가까운 무언가를 찾는 문제에서는 DFS보다는 BFS를 활용한다고 생각하면 된다고 한다. 그래서 다시 BFS 방식으로 작성해서 제출해본 결과 통과할 수는 있었지만 성능이 충격적일 정도로 낮게 나왔다.

왜 이런가 하니 내가 작성한 코드에서는 주어진 배열의 모든 요소에 대해서 BFS 탐색으로 거리 값을 계산하기 때문에 그만큼 오래 걸렸던 것 같다. 즉 한 번에 하나의 셀에 대해서만 거리를 계산할 수 있는데 그 거리를 계산하기 위해서 여러 셀을 탐색하다 보니 시간이 너무 오래 걸렸던 것이다. 이를 개선하기 위한 방안을 찾아보니 BFS 탐색과 동시에 셀의 거리를 업데이트하는 방법이 있었다.

이 방법은 기본적으로 결과 배열에서 0셀이 아닌 셀을 9999 같은 매우 높은 값으로 초기화한다. 문제에서는 10000개 이상의 셀이 주어지지 않기 때문에 9999나 10000 같은 값으로 지정해도 충분하다. 그리고 이번에는 1셀이 아니라 0셀을 기준으로 BFS 탐색하며 주변 셀의 거리 값을 업데이트하는 방식이다.

예를 들어 위의 배열에서 0셀만 탐색한다면 (0, 0), (0, 2), (1, 0), (1, 2), (2, 1) 셀만 탐색하게 된다. 이때 BFS 탐색이기 때문에 큐를 하나 생성해서 이 0셀들을 삽입해야 하며 그중 가장 먼저 탐색하게 되는 (0, 0) 셀을 기준으로 탐색하면 다음과 같다.

• (0, 0)의 왼쪽, 위쪽 셀에는 접근할 수 없기 때문에 참조하지 않는다.

• (0, 0)의 오른쪽 셀은 거리 값(9999)이 현재 셀의 거리 값+1(0+1) 보다 높기 때문에 현재 셀의 거리 값으로 업데이트하고 오른쪽 셀을 BFS 탐색 큐에 삽입한다.

• (0, 0)의 아래쪽 셀은 거리 값(0)이 현재 셀의 거리 값+1(0+1) 보다 높지 않기 때문에 업데이트하지 않고 더 이상 탐색하지 않는다.

• 큐에서 새로운 셀을 하나 꺼내서 다시 탐색한다.

이게 무슨 원리냐면 탐색하는 상하좌우 셀의 거리 값이 현재 셀의 거리 값+1, 즉 현재 셀에서 이동했을 때의 거리 값보다 크다면 해당 셀로 이동하는 더 작은 거리 값을 발견했기 때문에 업데이트해주고 추가적으로 탐색하기 위해 큐에 삽입해주는 방식이다. 결과 배열을 초기화할 때 0셀이 아닌 셀들의 거리 값을 전부 10000 같은 큰 값으로 저장했기 때문에 결과 배열에서 0셀의 근처에 있는 1셀들은 전부 새로운 거리 값으로 업데이트된다. 그리고 같은 0셀이나 이미 다른 0셀의 탐색에서 자신보다 짧은 거리 값으로 업데이트된 1셀을 탐색할 때는 업데이트하지 않는 방식이다. 한 번의 탐색에서 여러 개의 셀을 업데이트할 수 있기 때문에 굳이 BFS 탐색을 여러 번 할 필요가 없어 더 효율적이었다.

성능은 확실히 개선되긴 했지만 그래도 결과가 딱히 좋진 않은데 뭐가 문제일까? 이는 저번에 다른 풀이에서 본 "1,2"같은 문자열로 방문한 좌표를 기억하는 방법이 문제였다. 좌표값을 기억하기 위해 문자열을 생성하고 다시 split 해서 파싱 하는 과정이 꽤 시간을 많이 차지했기 때문에 이를 Integer 배열로 바꿔서 다음과 같이 개선하니 훨씬 빠른 결과를 얻을 수 있었다.

import java.util.LinkedList;


class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        LinkedList<Integer[]> queue = new LinkedList<>();
        
        int[][] result = new int[rows][cols];
        for(int row = 0; row < rows; row++){
            for(int col = 0; col < cols; col++){
                if(matrix[row][col] == 0) {
                    result[row][col] = 0;
                    queue.add(new Integer[]{row,col});
                }
                else {
                    result[row][col] = 10000;
                } 
            }
        }
        
        while(queue.size() > 0){
            Integer[] location = queue.pop();                    
            int currentRow = location[0];
            int currentCol = location[1];

            if(currentRow > 0){
                if(result[currentRow-1][currentCol] > result[currentRow][currentCol]+1){
                    result[currentRow-1][currentCol] = result[currentRow][currentCol]+1;
                    queue.add(new Integer[]{currentRow-1,currentCol});
                }
            }
            if(currentRow < rows-1){
                if(result[currentRow+1][currentCol] > result[currentRow][currentCol]+1){
                    result[currentRow+1][currentCol] = result[currentRow][currentCol]+1;
                    queue.add(new Integer[]{currentRow+1,currentCol});
                }
            }
            if(currentCol > 0){
                if(result[currentRow][currentCol-1] > result[currentRow][currentCol]+1){
                    result[currentRow][currentCol-1] = result[currentRow][currentCol]+1;
                    queue.add(new Integer[]{currentRow,currentCol-1});
                }
            }
            if(currentCol < cols-1){
                if(result[currentRow][currentCol+1] > result[currentRow][currentCol]+1){
                    result[currentRow][currentCol+1] = result[currentRow][currentCol]+1;
                    queue.add(new Integer[]{currentRow,currentCol+1});
                }
            }
        }
        
        return result;
    }

}

이를 좀 더 개선한 버전(7ms)으로 다른 사람이 작성한 다음과 같은 풀이를 볼 수 있었다.

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int m=matrix.length;
        if(m == 0)
            return null;
        int n = matrix[0].length;
        
        int[][] ans=new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j] != 0)
                    ans[i][j]=Integer.MAX_VALUE-1;
            }
        }
        
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                if(matrix[i][j] == 0)
                    continue;
                if(i-1 >= 0){
                    ans[i][j]=Math.min(ans[i][j], ans[i-1][j]+1);
                }
                if(i+1 < m)
                    ans[i][j]=Math.min(ans[i][j], ans[i+1][j]+1);
                if(j-1 >= 0)
                    ans[i][j]=Math.min(ans[i][j], ans[i][j-1]+1);
                if(j+1 < n)
                    ans[i][j]=Math.min(ans[i][j], ans[i][j+1]+1);
            }
        }
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j] == 0)
                    continue;
                if(i-1 >= 0){
                    ans[i][j]=Math.min(ans[i][j], ans[i-1][j]+1);
                }
                if(i+1 < m)
                    ans[i][j]=Math.min(ans[i][j], ans[i+1][j]+1);
                if(j-1 >= 0)
                    ans[i][j]=Math.min(ans[i][j], ans[i][j-1]+1);
                if(j+1 < n)
                    ans[i][j]=Math.min(ans[i][j], ans[i][j+1]+1);
            }
        }
        return ans;
    }
}

특이하게 2중 for 문을 두 번 반복하는데 첫 번째는 결과 배열의 처음부터, 두 번째는 결과 배열의 마지막부터 탐색하며 현재 셀과 인접한 셀의 거리 값을 비교한다. 이번 결과 배열도 0셀이 아닌 셀에는 Integer.MAX_VALUE-1 같은 매우 큰 값을 저장해 두고 있는데 중요한 것은 한 줄씩 순서대로 탐색하면서 0셀이 아닌 셀의 현재 거리 값과 인접한 셀의 거리 값+1을 비교하여 더 작은 값을 현재 셀의 거리 값으로 저장하는 방법을 모든 셀에 대하여 반복하고 있는 것이다.

예를 들어 위와 같은 셀이 있다고 할 때 맨 끝에서부터 탐색하는 첫 번째 for문은 다음과 같이 진행된다.

맨 오른쪽 아래 셀 (2, 3)에서는 위의 셀 (1, 3)가 거리 값 0+1을 갖고 있기 때문에 현재 셀의 거리 값 9999보다 작으므로 현재 셀의 거리 값을 1로 업데이트한다. 왼쪽 셀 (2, 2)은 거리 값 9999+1을 갖고 있기 때문에 현재 셀의 거리 값 1보다 작지 않으므로 업데이트하지 않는다. 인접 셀의 거리 값에 1을 더하는 이유는 언급했듯이 셀 간 이동거리기 때문이다. 이렇게 하나씩 업데이트하다 보면 모든 셀의 거리 값을 업데이트할 수 있는데 그러면 왜 굳이 다른 방향으로 한번 더 반복하는 것일까? 이는 다음과 같은 경우를 대비하기 위해서다.

위의 배열에서는 아까처럼 배열의 맨 마지막부터 탐색하는 경우 3번째 행에 있는 셀들의 거리 값을 업데이트할 수 없다. 왜냐면 인접 셀만 검사하는 방법 특성상 3번째 행에 인접한 2번째 행들도 모두 최대 거리 값을 갖고 있기 때문이다.

이전처럼 (2, 3) 셀부터 탐색한다면 왼쪽, 위 셀들의 거리 값 9999+1은 현재 셀의 거리 값 9999보다 작지 않기 때문에 업데이트되지 않는다. 동일하게 (2, 2), (2, 1), (2, 0) 셀들도 그럴 것이다. 그러나 (1, 0) ~ (1, 3) 셀들은 자신의 위에 있는 행에 속한 셀의 거리 값 0+1과 비교하여 거리 값을 업데이트할 수 있기 때문에 다음과 같이 변경될 것이다.

그러면 어차피 한번 탐색할 때마다 그래도 한 줄씩 갱신되니까 그냥 끝에서부터 탐색하는 과정을 몇 번 더 반복하면 되지 않느냐?라고 생각할 수 있지만 위의 두 번째, 세 번째 행처럼 0셀이 인접해있지 않는 행이 얼마나 있을지 모르기 때문에 몇 번씩 반복하는 것보다는 한번 반대로 탐색하는 방식이 훨씬 효과적일 것이다.

처음부터 탐색한다면 (2, 0) 셀에서는 (1, 0) 셀의 거리 값 1+1이 자신의 거리 값 9999보다 작기 때문에 1+1로 업데이트해준다. (2, 1) 셀에서도 (1, 1) 셀의 거리 값 1+1이 자신의 거리 값 9999보다 작기 때문에 1+1로 업데이트해주는데 (2, 0) 셀의 거리 값 2+1은 (1, 1) 셀의 거리 값으로 업데이트된 1+1보다 작지 않기 때문에 업데이트하지 않는다. 이런 방식으로 최소 거리 값만 셀에 저장할 수 있는 것이다.

 

이건 BFS라기보다는 그냥 엄청 효율적인 방법인 걸까? 어떤 알고리즘으로 분류해야 할지 잘 모르겠다. 하지만 굉장히 간단하고 창의적인 방법이라고 느낄 수 있었다.

 

 

BFS 탐색만 하면 항상 방문한 셀을 기억하고 주변의 이웃 셀을 큐에 집어넣어서 방문하는 방법만 생각했는데 이번처럼 문제의 특징에 따라 맨 처음 거리 값을 최댓값으로 설정해두고. 특히 맨 처음에 문제 풀이 방향을 잘못 잡아서 DFS 탐색 방법을 시도했던 게 정말 기억에 남는다. 언급했지만 'closest'가 나오면 'BFS'를 생각하라는 댓글을 머릿속에 잘 새겨둬야겠다.