Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀이하는 01 행렬 문제 – 각 셀에서 가장 가까운 0까지의 거리 구하기

문제 설명

0과 1로만 이루어진 행렬이 주어졌을 때, 각 셀에서 가장 가까운 0까지의 거리를 구하는 것이 목표입니다. 이때 인접한 두 셀 사이의 거리는 1로 정의됩니다.

예를 들어 입력이 다음과 같다면,

000
010
111

출력은 다음과 같습니다.

000
010
121

행렬 중앙의 1은 바로 옆에 0이 인접해 있으므로 거리가 1이 되고, 마지막 행의 가운데 1은 인접한 네 방향 어디에도 0이 없으므로 두 칸 떨어진 0까지의 거리인 2가 됩니다.

접근 방법: 너비 우선 탐색(BFS)

이 문제는 너비 우선 탐색(BFS)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 모든 0인 셀을 시작점으로 큐에 넣고, 레벨(level) 단위로 인접한 셀들을 확장해 나가면서 각 셀의 최단 거리를 기록하는 것입니다.

알고리즘 단계

  • 크기가 4×2인 방향 배열 dir을 {{1, 0}, {-1, 0}, {0, -1}, {0, 1}}로 정의합니다. 이는 상·하·좌·우 네 방향의 이동을 나타냅니다.

  • n := 행의 개수, m := 열의 개수로 설정합니다.

  • n × m 크기의 결과 행렬 ret를 정의하고, 모든 값을 무한대(inf)로 초기화합니다.

  • 큐 q를 하나 생성합니다.

  • i := 0부터 i < n일 때까지 i를 1씩 증가시키며 반복합니다.

    • j := 0부터 j < m일 때까지 j를 1씩 증가시키며 반복합니다.

      • 만약 matrix[i, j]의 값이 0이라면 다음을 수행합니다.

        • ret[i, j] := 0 으로 설정

        • {i, j} 좌표를 큐 q에 삽입

  • lvl := 1부터 시작하여 큐가 비어 있지 않은 동안 반복하며, 매 반복마다 lvl을 1씩 증가시킵니다.

    • sz := 큐의 현재 크기

    • sz가 0이 될 때까지 매 반복마다 sz를 1씩 감소시키며 다음을 수행합니다.

      • curr := 큐의 맨 앞(front) 요소

      • 큐에서 해당 요소를 제거(pop)

      • k := 0부터 k < 4일 때까지 k를 1씩 증가시키며 반복합니다.

        • nx := curr.first + dir[k][0]

        • ny := curr.second + dir[k][1]

        • nx < 0 또는 nx ≥ n 또는 ny < 0 또는 ny ≥ m 또는 ret[nx, ny] < lvl인 경우에는 건너뜁니다(continue).

        • 그렇지 않으면 ret[nx, ny] := lvl로 설정하고, {nx, ny}를 큐 q에 삽입합니다.

  • 모든 과정이 끝나면 ret를 반환합니다.

C++ 구현 예제

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
   vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
   int n = matrix.size();
   int m = matrix[0].size();
   vector < vector <int> > ret(n, vector <int>(m, INT_MAX));
   queue < pair <int, int> > q;
   for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
         if(!matrix[i][j]){
            ret[i][j] = 0;
            q.push({i, j});
         }
      }
   }
   for(int lvl = 1; !q.empty(); lvl++){
      int sz = q.size();
      while(sz--){
         pair <int, int> curr = q.front();
         q.pop();
         for(int k = 0; k < 4; k++){
            int nx = curr.first + dir[k][0];
            int ny = curr.second + dir[k][1];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m || ret[nx][ny] < lvl) continue;
               ret[nx][ny] = lvl;
               q.push({nx, ny});
           }
        }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,0,0},{0,1,0},{1,1,1}};
   print_vector(ob.updateMatrix(v));
}

입력

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

출력

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

복잡도 분석

각 셀은 최대 한 번씩 큐에 삽입되고 제거되므로, 이 알고리즘의 시간 복잡도는 O(n × m)입니다. 공간 복잡도 역시 결과 행렬과 큐에 저장되는 좌표 때문에 O(n × m)입니다. 단순히 각 1인 셀마다 전체 행렬을 탐색하는 브루트 포스 방식(O((n × m)²))보다 훨씬 효율적이라는 점이 이 접근법의 가장 큰 장점입니다.