class Solution {
    
    // return the distance of the nearest 0 for each cell.
    // BFS
    // T: O(r*c)
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length; // The distaye of cells is up to (M+N)
        
        Queue<int[]> q = new ArrayDeque<>();
        
        // 모든 0인 셀을 큐에 저장한다.
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                if (mat[r][c] == 0) {
                    q.offer(new int[]{r, c});
                } else {
                    mat[r][c] = -1; // Marked as not processed yet!
                }
            }
        }
        
        // 상하좌우
        int[][] directions = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            // 값이 0인 셀의 인접한 상하좌우 셀을 처리한다.
            for (int[] dir : directions) {
                int x = curr[0] + dir[0], y = curr[1] + dir[1];
                // 경계조건 및 처리여부 체크
                if (x < 0 || x == m || y < 0 || y == n || mat[x][y] != -1) continue;
                // 값이 0인 인접 셀의 값에 +1 
                mat[x][y] = mat[curr[0]][curr[1]] + 1;
                // 인접 셀 처리를 하기 위해서 큐에 넣는다.
                q.offer(new int[]{x, y});
            }
        }
        
        return mat;
    }
}