C++로 구현하는 2D 그리드 시프트(Shift) 알고리즘

크기가 m x n인 2차원 그리드와 정수 k가 주어졌을 때, 그리드를 k번 시프트(이동)해야 하는 문제를 생각해 봅시다. 시프트 연산은 다음 규칙에 따라 수행됩니다.

• 그리드의 요소 G[i, j]는 G[i, j + 1] 위치로 이동합니다.
• 각 행의 마지막 요소 G[i, n – 1]은 다음 행의 첫 번째 위치 G[i + 1, 0]으로 이동합니다.
• 그리드의 마지막 요소 G[m - 1, n – 1]은 첫 번째 위치 G[0, 0]으로 이동합니다.

예를 들어 그리드가 다음과 같다고 가정해 보겠습니다.

한 번 시프트를 수행하면 결과는 다음과 같습니다.

문제 해결 접근 방법

이 문제는 마치 1차원 배열을 오른쪽으로 한 칸씩 밀듯이, 2차원 그리드 전체를 일렬로 펼쳐서 순환 이동하는 것과 같습니다. 해결 절차는 다음과 같습니다.

• 시프트 함수는 행렬을 입력으로 받습니다.
• n := 행의 개수, m := 열의 개수로 설정하고, x에 가장 오른쪽 아래 요소(마지막 요소)를 저장합니다. 이 값은 덮어쓰기 전에 반드시 보관해야 합니다.
• i를 n – 1부터 0까지 감소시키며 반복합니다.
  • j를 m – 1부터 0까지 감소시키며 반복합니다.
    • j = 0이고 i > 0이라면, G[i, j] := G[i – 1, m - 1] (바로 위 행의 마지막 값을 가져옵니다)
    • 그렇지 않고 j > 0이라면, G[i, j] := G[i, j – 1] (왼쪽 요소의 값을 가져옵니다)
• 마지막으로 G[0, 0] := x를 대입하여 처음 보관했던 값을 첫 번째 위치에 넣습니다.
• 위 규칙에 따라 시프트 연산을 호출합니다.
• k가 0이 아닌 동안
  • 그리드 G를 시프트합니다.
  • k를 1씩 감소시킵니다.
• 모든 반복이 끝나면 그리드 G를 반환합니다.

C++ 구현 예제

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > 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;
}
class Solution {
public:
   void shift(vector<vector<int>>& grid){
      int n = grid.size();
      int m = grid[0].size();
      int x = grid[n-1][m-1];
      for(int i = n-1; i>=0; i--){
         for(int j = m-1;j>=0;j--){
            if(j == 0 && i>0){
               grid[i][j] = grid[i-1][m-1];
            }
            else if(j>0){
               grid[i][j] = grid[i][j-1];
            }
         }
      }
      grid[0][0] = x;
   }
   vector<vector<int>> shiftGrid(vector<vector<int>>& g, int k) {
      while(k--){
         shift(g);
      }
      return g;
   }
};
main(){
   Solution ob;
   vector<vector<int>> mat = {{1,2,3},{4,5,6},{7,8,9}};
   print_vector(ob.shiftGrid(mat, 1));
}

입력

{{1,2,3},{4,5,6},{7,8,9}}
1

출력

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