[LeetCode] 01 Matrix (Java)

leetcode.com/problems/01-matrix/

01 Matrix - LeetCode

사용 알고리즘 : 너비 우선 탐색(Breadth-first search, BFS)

 

문제 : M x N 행렬이 0과 1로 구성된 경우 각 셀에 대해 가장 가까운 0의 거리를 찾는 것 이다.

 

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

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

 

접근 아이디어 :

1. 행렬의 값이 0인 경우 1까지의 거리를 구하도록 한다. (단 1과 인접한 방향에 있는 경우에 한해서)

2. 행렬이 0인 경우 Queue에 좌표 배열을 넣으면서 방문 처리를 해준다. (여기서 포인트는 0인 경우 방문처리이다)

3. Queue 크기를 이용하여 한 싸이클을 기준으로 반복문을 돌린다. (모든 인접한 0에 대해 최소한의 거리를 가져야 하기 때문이다)

4. 나머지는 기본 BFS 구현 문제와 비슷하다.

 

class Solution {
    
    final int[][] dirs = {{0, 1},{1, 0},{0, -1},{-1, 0}};
    
    public int[][] updateMatrix(int[][] matrix) {
        int col = matrix.length;
        int row = matrix[0].length;
        boolean[][] visit = new boolean[col][row];
        Queue<int[]> queue = new LinkedList<>();
        for(int i=0; i<col; i++) {
            for(int j=0; j<row; j++) {
                if(matrix[i][j] == 0) {
                    visit[i][j] = true;
                    queue.add(new int[]{i, j});
                }
            }
        }
        
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size-- > 0) {
                int[] cur = queue.poll();
                int curX = cur[0];
                int curY = cur[1];
                for(int[] dir : dirs) {
                    int nextX = curX + dir[0];
                    int nextY = curY + dir[1];
                    if(isNotRange(nextX, nextY, col, row)) continue;
                    if(visit[nextX][nextY]) continue;     
                    queue.add(new int[] {nextX, nextY});
                    visit[nextX][nextY] = true;
                    matrix[nextX][nextY] = matrix[curX][curY] + 1;
                }
            }
        }
        
        return matrix;
    }
    
    boolean isNotRange(int x, int y, int col, int row) {
        return (x < 0 || y < 0 || x >= col || y >= row ? true : false);
    }
}