이진 행렬에서 1을 갖는 가장 가까운 셀의 거리

난이도 하드
자주 묻는 질문 Accenture 아마존 하니웰 HSBC 훌루 Twitter
배열 폭 우선 검색 Graph 매트릭스 조회수 30

문제 정책

"이진 행렬에서 1을 갖는 가장 가까운 셀의 거리"문제는 이진법이 주어 졌다는 것입니다. 매트릭스(0과 1 만 포함) 1 개 이상 포함. 행렬의 모든 요소에 대해 이진 행렬에서 1을 갖는 가장 가까운 셀의 거리를 찾습니다. 여기서 두 셀 (x1, y1)과 (x2, y2) 사이의 거리 )는 | x2 – x1 | + | y2 – y1 |.

{
{0, 1, 0}
{0, 0, 0}
{1, 0, 0}
}
{
{1, 0, 1}
{1, 1, 2}
{0, 1, 2}
}

설명: 결과 행렬에서 1을 갖는 셀은 0이고 1을 갖는 셀과 1의 거리에있는 셀을 볼 수 있습니다.이 셀은 출력으로 1을 가지며 마찬가지로 다른 셀에 대해서도 거리를 계산했습니다.

{
{0, 0, 0}
{0, 0, 0}
{1, 0, 1}
}
{
{2, 3, 2}
{1, 2, 1}
{0, 1, 0}
}

순진한 접근

행렬의 모든 요소에 대해 전체 매트릭스 행렬에서 최소 거리가 1 인 셀을 찾습니다.

  1. 배열 행렬과 같은 크기의 배열 ans를 만듭니다. 두 개의 중첩 루프를 실행하여 행렬의 모든 요소를 ​​순회합니다.
  2. 행렬의 각 요소에 대해 두 개의 중첩 루프를 더 실행하여 행렬의 각 요소를 탐색합니다.이를 현재 요소로 할 수 있습니다. 현재 1 인 모든 요소에 대해 최소 거리 요소를 찾고 해당 거리를 ans 배열에 저장합니다.
  3. ans 배열을 인쇄합니다.

복잡성 분석

시간 복잡성 = 의 위에2 * 미디엄2)
공간 복잡성 = O (n * m)
여기서 n과 m은 각각 주어진 행렬의 행과 열입니다.

행렬의 각 셀에 대해 전체 행렬을 순회하고 있기 때문입니다. 이것은 알고리즘이 더 높은 시간 복잡도로 실행되도록합니다. 공간 복잡성은 출력을 저장하기 때문이지만 알고리즘 자체에는 일정한 공간이 필요합니다. 단순히 출력물을 인쇄했다면이 공간 복잡성도 줄어들었을 것입니다.

암호

이진 행렬에서 1을 갖는 가장 가까운 셀의 거리를 찾는 Java 코드

class DistanceOfNearestCellHaving1InABinaryMatrix {
    private static void minimumDistance(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;

        int[][] ans = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int minDist = Integer.MAX_VALUE;
                for (int x = 0; x < n; x++) {
                    for (int y = 0; y < m; y++) {
                        if (matrix[x][y] == 1) {
                            int dist = Math.abs(x - i) + Math.abs(y - j);
                            minDist = Math.min(minDist, dist);
                        }
                    }
                }
                ans[i][j] = minDist;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(ans[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int matrix1[][] = new int[][]{
                {0, 1, 0},
                {0, 0, 0},
                {1, 0, 0}
        };
        minimumDistance(matrix1);

        int matrix2[][] = new int[][]{
                {0, 0, 0},
                {0, 0, 0},
                {1, 0, 1}
        };
        minimumDistance(matrix2);
    }
}
1 0 1 
1 1 2 
0 1 2 

2 3 2 
1 2 1 
0 1 0

이진 행렬에서 1을 갖는 가장 가까운 셀의 거리를 찾는 C ++ 코드

#include<bits/stdc++.h> 
using namespace std; 

void minimumDistance(vector<vector<int>> &matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    
    int ans[n][m];
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int minDist = INT_MAX;
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < m; y++) {
                    if (matrix[x][y] == 1) {
                        int dist = abs(x - i) + abs(y - j);
                        minDist = std::min(minDist, dist);
                    }
                }
            }
            ans[i][j] = minDist;
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
              cout<<ans[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

int main() {
    // Example 1
    vector<vector<int>> matrix1 = {
            {0, 1, 0},
            {0, 0, 0},
            {1, 0, 0}
    };
    minimumDistance(matrix1);

    // Example 2
    vector<vector<int>> matrix2 = {
            {0, 0, 0},
            {0, 0, 0},
            {1, 0, 1}
    };
    minimumDistance(matrix2);
    
    return 0;
}
1 0 1 
1 1 2 
0 1 2 

2 3 2 
1 2 1 
0 1 0

최적의 접근 방식

더 나은 접근 방식은 주어진 행렬의 모든 1에서 시작하여 BFS를 수행하는 것입니다. 모든 1의 거리는 XNUMX이고 모든 인접의 최소 거리는 이보다 하나 더 큽니다.

  1. 만들기 변발 요소의 (행, 열)을 저장하는 데 사용되는 좌표. 만들기 정렬 배열과 같은 크기의 ans 매트릭스.
  2. 행렬의 모든 요소를 ​​가로 질러 1 인 요소의 좌표를 대기열에 넣습니다.
  3. 변수 minDistance를 0으로 초기화합니다. 대기열이 비어 있지 않은 동안 4 단계와 5 단계를 반복합니다.
  4. 큐 크기로 변수 크기를 초기화합니다. i가 0과 크기 (포함되지 않음) 인 경우 루프를 실행합니다. 반복 할 때마다 큐에서 요소가 나타납니다. ans [row] [col]을 minDistance로 설정하고 행렬 배열에서 0 인이 요소의 모든 유효한 인접 항목을 대기열에 넣고 행렬 배열에서 1로 설정합니다.
  5. minDistance를 증가시킵니다.
  6. ans 배열을 인쇄합니다.

복잡성 분석

시간 복잡성 = O (n * m)
공간 복잡성 = O (n * m)
여기서 n과 m은 각각 주어진 행렬의 행과 열입니다.

알고리즘은 그래프의 BFS와 매우 유사하므로 O (N * M) 시간 만 사용되었습니다.

설명

예를 고려하십시오.
{
{0, 1, 0}
{0, 0, 0}
{1, 0, 0}
}

이진 행렬에서 1을 갖는 가장 가까운 셀의 거리

암호

이진 행렬에서 1을 갖는 가장 가까운 셀의 거리를 찾는 Java 코드

import java.util.LinkedList;
import java.util.Queue;
class Optimal {
    private static void minimumDistance(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;

        // create an array ans of size same as matrix array
        int ans[][] = new int[n][m];

        // create a queue of coordinates
        // push all the elements that are equals to 1 in the matrix array to the queue
        Queue<Coordinate> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 1) {
                    queue.add(new Coordinate(i, j));
                }
            }
        }

        // initialize minDistance as 0
        int minDistance = 0;

        while (!queue.isEmpty()) {
            // initialize size as size of queue
            int size = queue.size();

            // Run a loop size times
            for (int i = 0; i < size; i++) {
                // remove an element from queue
                Coordinate curr = queue.poll();

                // ans to this coordinate is minDistance
                ans[curr.row][curr.col] = minDistance;

                // enqueue all the valid adjacent cells of curr that are equals to
                // 0 in the matrix array and set them as 1

                // left adjacent
                int leftRow = curr.row - 1;
                int leftCol = curr.col;
                if ((leftRow >= 0 && leftRow < n) && (leftCol >= 0 && leftCol < m)) {
                    if (matrix[leftRow][leftCol] == 0) {
                        queue.add(new Coordinate(leftRow, leftCol));
                        matrix[leftRow][leftCol] = 1;
                    }
                }

                // right adjacent
                int rightRow = curr.row + 1;
                int rightCol = curr.col;
                if ((rightRow >= 0 && rightRow < n) && (rightCol >= 0 && rightCol < m)) {
                    if (matrix[rightRow][rightCol] == 0) {
                        queue.add(new Coordinate(rightRow, rightCol));
                        matrix[rightRow][rightCol] = 1;
                    }
                }

                // up adjacent
                int upRow = curr.row;
                int upCol = curr.col + 1;
                if ((upRow >= 0 && upRow < n) && (upCol >= 0 && upCol < m)) {
                    if (matrix[upRow][upCol] == 0) {
                        queue.add(new Coordinate(upRow, upCol));
                        matrix[upRow][upCol] = 1;
                    }
                }

                // down adjacent
                int downRow = curr.row;
                int downCol = curr.col - 1;
                if ((downRow >= 0 && downRow < n) && (downCol >= 0 && downCol < m)) {
                    if (matrix[downRow][downCol] == 0) {
                        queue.add(new Coordinate(downRow, downCol));
                        matrix[downRow][downCol] = 1;
                    }
                }
            }

            // increment minimum distance
            minDistance++;
        }

        // print the elements of the ans array
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(ans[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        int matrix1[][] = new int[][]{
                {0, 1, 0},
                {0, 0, 0},
                {1, 0, 0}
        };
        minimumDistance(matrix1);

        // Example 2
        int matrix2[][] = new int[][]{
                {0, 0, 0},
                {0, 0, 0},
                {1, 0, 1}
        };
        minimumDistance(matrix2);
    }

    // class representing coordinates of a cell in matrix
    static class Coordinate {
        int row;
        int col;

        public Coordinate(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}
1 0 1 
1 1 2 
0 1 2 

2 3 2 
1 2 1 
0 1 0

이진 행렬에서 1을 갖는 가장 가까운 셀의 거리를 찾는 C ++ 코드

#include<bits/stdc++.h> 
using namespace std; 

// class representing coordinates of a cell in matrix
class Coordinate {
    public:
    int row;
    int col;
    
    Coordinate(int r, int c) {
        row = r;
        col = c;
    }
};

void minimumDistance(vector<vector<int>> &matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    
    // create an array ans of size same as matrix array
    int ans[n][m];
    
    // create a queue of coordinates
    // push all the elements that are equals to 1 in the matrix array to the queue
    queue<Coordinate> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 1) {
                Coordinate coordinate(i, j);
                q.push(coordinate);
            }
        }
    }
    
    // initialize minDistance as 0
    int minDistance = 0;
    
    while (!q.empty()) {
        // initialize size as size of queue
        int size = q.size();
        
        // Run a loop size times
        for (int i = 0; i < size; i++) {
            // remove an element from queue
            Coordinate curr = q.front();
            q.pop();
            
            // ans to this coordinate is minDistance
            ans[curr.row][curr.col] = minDistance;
            
            // enqueue all the valid adjacent cells of curr that are equals to
            // 0 in the matrix array and set them as 1
            
            // left adjacent
            int leftRow = curr.row - 1;
            int leftCol = curr.col;
            if ((leftRow >= 0 && leftRow < n) && (leftCol >= 0 && leftCol < m)) {
                if (matrix[leftRow][leftCol] == 0) {
                    Coordinate cLeft(leftRow, leftCol);
                    q.push(cLeft);
                    matrix[leftRow][leftCol] = 1;
                }
            }
            
            // right adjacent
            int rightRow = curr.row + 1;
            int rightCol = curr.col;
            if ((rightRow >= 0 && rightRow < n) && (rightCol >= 0 && rightCol < m)) {
                if (matrix[rightRow][rightCol] == 0) {
                    Coordinate cRight(rightRow, rightCol);
                    q.push(cRight);
                    matrix[rightRow][rightCol] = 1;
                }
            }
            
            // up adjacent
            int upRow = curr.row;
            int upCol = curr.col + 1;
            if ((upRow >= 0 && upRow < n) && (upCol >= 0 && upCol < m)) {
                if (matrix[upRow][upCol] == 0) {
                    Coordinate cUp(upRow, upCol);
                    q.push(cUp);
                    matrix[upRow][upCol] = 1;
                }
            }
            
            // down adjacent
            int downRow = curr.row;
            int downCol = curr.col - 1;
            if ((downRow >= 0 && downRow < n) && (downCol >= 0 && downCol < m)) {
                if (matrix[downRow][downCol] == 0) {
                    Coordinate cDown(downRow, downCol);
                    q.push(cDown);
                    matrix[downRow][downCol] = 1;
                }
            }
        }
        
        // increment minimum distance
        minDistance++;
    }
    
    // print the elements of the ans array
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout<<ans[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

int main() {
    // Example 1
    vector<vector<int>> matrix1 = {
            {0, 1, 0},
            {0, 0, 0},
            {1, 0, 0}
    };
    minimumDistance(matrix1);

    // Example 2
    vector<vector<int>> matrix2 = {
            {0, 0, 0},
            {0, 0, 0},
            {1, 0, 1}
    };
    minimumDistance(matrix2);
    
    return 0;
}
1 0 1 
1 1 2 
0 1 2 

2 3 2 
1 2 1 
0 1 0
Translate »