C++의 대각선 트래버스

M x N 요소의 행렬이 있다고 가정하면 행렬의 모든 요소를 ​​대각선 순서로 찾아야 합니다. 따라서 행렬이 다음과 같은 경우 -

출력은 [1,2,4,7,5,3,6,8,9]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 배열을 ret로 만들고 row :=0 및 col :=0, n :=row count, m :=col count, down :=false로 설정
• 0 ~ n – 1 범위의 i에 대해
  • x :=i, y :=0
  • 배열 임시 생성
  • x>=0이고 y
  • 매트릭스[x,y]를 temp에 삽입하고 x를 1만큼 감소시키고 y를 1만큼 증가시킵니다.
• down이 참이면 임시 배열을 반대로 합니다.
• 0에서 temp – 1의 크기 범위에 있는 i의 경우 temp[i]를 ret에 삽입
• 아래로 :=아래로의 역

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
      vector <int> ret;
      int row = 0;
      int col = 0;
      int n = matrix.size();
      int m = n? matrix[0].size() : 0;
      bool down = false;
      for(int i = 0; i < n; i++){
         int x = i;
         int y = 0;
         vector <int> temp;
         while(x >= 0 && y < m){
            temp.push_back(matrix[x][y]);
            x--;
            y++;
         }
         if(down) reverse(temp.begin(), temp.end());
         for(int i = 0; i < temp.size(); i++)ret.push_back(temp[i]);
         down = !down;
      }
      for(int i = 1; i < m; i++){
         int x = n - 1;
         int y = i;
         vector <int> temp;
         while(x >= 0 && y < m){
            temp.push_back(matrix[x][y]);
            x--;
            y++;
         }
         if(down) reverse(temp.begin(), temp.end());
         for(int i = 0; i < temp.size(); i++)ret.push_back(temp[i]);
         down = !down;
      }
      return ret;
   }
};
main(){
   vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
   Solution ob;
   print_vector(ob.findDiagonalOrder(v));
}

입력

[[1,2,3],[4,5,6],[7,8,9]]

출력

[1, 2, 4, 7, 5, 3, 6, 8, 9, ]