알고리즘 :: 백준 :: 시뮬레이션 :: 16935 :: 배열 돌리기3

문제

문제접근

문제 이해

문제에 주어진 조건들을 그대로 코드로 구현하는 전형적인 '시뮬레이션' 유형입니다.

문제를 편하게 설명하기 위해 배열을 $N \times M$ 형태의 배열 a라 가정하겠습니다.

연산은 (1, 2) → (3, 4) → (5, 6) 순으로 구현이 어렵습니다.

최대한 RangeException에 신경쓰면서 인덱스를 조작해보며 구현합니다.

1번 연산 - 상하 반전

• 배열을 상하 반전하기 위해서는 i번째 행과 N-1-i번째 행을 서로 교환해주면 됩니다.

• 주의할 점은 $N / 2$ 번째 행까지만 반전해주면 된다는 점입니다.

  • 만일 $N$번째 행까지 반전을 계속한다면 다시 원상복귀 되겠죠?

• 서로 대칭된 위치에 있는 두 행을 교환하는 방법은 두 가지가 있습니다.

  1. 각 요소끼리 교환합니다.

     for (int y = 0; y < N; ++y) {
         for (int x = 0; x < M; ++x) {
             tmp = a[y][x];
             a[y][x] = a[N - 1 - y][x];
             a[N - 1 - y][x] = tmp;
             // swap(a[y][x], a[N - 1 - y][x]);
         }
     }

2.  각 행끼리 교환합니다.

    ```cpp
    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < M; ++x) tmp[x] = a[y][x];
        for (int x = 0; x < M; ++x) a[y][x] = a[N - 1 - y][x];
        for (int x = 0; x < M; ++x) a[N - 1 - y][x] = tmp[x];
    }
    ```

2번 연산 - 좌우 반전

• 배열을 좌우 반전하기 위해서는i번째 열과 M-1-i번째 열을 서로 교환해주면 됩니다.

• 역시 $N / 2$번째 열까지만 반전해줘야 문제가 발생하지 않습니다.

• 반전하는 방식은 1번 연산과 동일합니다.

  for (int y = 0; y < N; ++y) {
      for (int x = 0; x < M / 2; ++x) {
          tmp[x] = a[y][x];
          a[y][x] = a[y][M - 1 - x];
          a[y][M - 1 - x] = tmp[x];
          // swap(a[y][x], a[y][M - 1 - x]);
      }
  }

3번, 4번 연산 - 좌우 회전

• 배열을 좌우로 90도 회전하는 연산은 PS에서 자주 등장하는 연산입니다.
  이번 기회에 잘 익혀둬서 자연스럽게 구사할 수 있도록 합니다.
• 회전은 행과 열을 바꾸면 됩니다.
  • 예를 들어, 왼쪽 회전하는 경우를 생각해봅시다.
  • (0, 0), (0, 1), (0, 2), (0, 3)은 (3, 0), (2, 0), (1, 0), (0, 0)으로 옮겨집니다.
  • (1, 0), (1, 1), (1, 2), (1, 3)은 (3, 1), (2, 1), (1, 1), (0, 1)로 옮겨집니다.
  • 규칙성이 보이시나요? (y, x)는 (M - 1 - x, y)로 옮겨집니다.
  • 그럼 오른쪽 회전은 어떻게 될까요? (y, x)는 (x, N - 1 - y)로 옮겨집니다.
  • 만일 이해가 안되신다면 꼭 손으로 그려보시면서 이해하시길 바랍니다.
• 주의해야할 점은 회전 시 N과 M이 바뀌어야 한다는 점입니다.
  • 예를 들어 $3 \times 5$ 배열은 회전 시 $5 \times 3$ 배열로 바뀝니다.

5번, 6번 연산 - 그룹 좌우 회전

• 이번에는 그룹에 대해 좌우 회전을 수행합니다.
• 그룹에 대한 좌우 회전은 3, 4번 연산과 달리 N과 M이 바뀌지 않습니다.
• 그룹에 대한 범위를 정의해야 합니다.
  • 1번 그룹: $0 \leq y < N/2$, $0 \leq x < M / 2$
  • 2번 그룹: $0 \leq y < N/2$, $M/2 \leq x < M$
  • 3번 그룹: $N/2 \leq y < N$, $M/2 \leq x < M$
  • 4번 그룹: $N/2 \leq y < N$, $0 \leq x < M / 2$
• 각 그룹을 회전할 때 원소들의 배치가 바뀌진 않으므로 단순히 범위만큼 감산해주면 됩니다.

코드

#include <iostream>
#include <vector>
using namespace std;

int N, M, R, op[1000];
vector<vector<int>> arr;

// 연산 1
void flipHorizontal() {
    for (int y = 0; y < N / 2; ++y)
        for (int x = 0; x < M; ++x)
            swap(arr[y][x], arr[N - 1 - y][x]);
}
// 연산 2
void flipvertical() {
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < M / 2; ++x) 
            swap(arr[y][x], arr[y][M - 1 - x]);
}
// 연산 3
void rotateRight() {
    vector<vector<int>> tmp(M, vector<int>(N));
    for (int y = N - 1; y >= 0; --y)
        for (int x = 0; x < M; ++x)
            tmp[x][N - 1 - y] = arr[y][x];
    swap(N, M);
    arr = tmp;
}
// 연산 4
void rotateLeft() {
	vector<vector<int>> tmp(M, vector<int>(N));
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < M; ++x)
			tmp[M - 1 - x][y] = arr[y][x];
	swap(N, M);
	arr = tmp;
}
// 연산 5
void rotateGroupRight() {
	vector<vector<int>> tmp(N, vector<int>(M));
    int halfRow = N / 2, halfCol = M / 2;
	for (int y = 0; y < halfRow; ++y)    
		for (int x = 0; x < halfCol; ++x)
			tmp[y][x + halfCol] = arr[y][x];    // Group 1 to 2
	for (int y = 0; y < halfRow; ++y)    
		for (int x = halfCol; x < M; ++x)
			tmp[y + halfRow][x] = arr[y][x];    // Group 2 to 3
	for (int y = halfRow; y < N; ++y)
		for (int x = halfCol; x < M; ++x)
			tmp[y][x - halfCol] = arr[y][x];    // Group 3 to 4
	for (int y = halfRow; y < N; ++y)
		for (int x = 0; x < halfCol; ++x)
			tmp[y - halfRow][x] = arr[y][x];    // Group 4 to 1  
	arr = tmp;
}
// 연산 6
void rotateGroupLeft() {
   vector<vector<int>> tmp(N, vector<int>(M));
    int halfRow = N / 2, halfCol = M / 2;
	for (int y = 0; y < halfRow; ++y)
		for (int x = 0; x < halfCol; ++x)
			tmp[y + halfRow][x] = arr[y][x];    // Group 1 to 4
	for (int y = 0; y < halfRow; ++y)
		for (int x = halfCol; x < M; ++x)
			tmp[y][x - halfCol] = arr[y][x];    // Group 2 to 1
	for (int y = halfRow; y < N; ++y)
		for (int x = halfCol; x < M; ++x)
			tmp[y - halfRow][x] = arr[y][x];    // Group 3 to 2
	for (int y = halfRow; y < N; ++y)
		for (int x = 0; x < halfCol; ++x)
			tmp[y][x + halfCol] = arr[y][x];    // Group 4 to 3
	arr = tmp;
}

void solve() {
   for (int i = 0; i < R; ++i) {
      switch(op[i]) {
         case 1: flipHorizontal(); break;
         case 2: flipvertical(); break;
         case 3: rotateRight(); break;
         case 4: rotateLeft(); break;
         case 5: rotateGroupRight(); break;
         case 6: rotateGroupLeft(); break;
      }
   }
}

void show() {
   for (int y = 0; y < N; ++y) {
      for (int x = 0; x < M; ++x)
         cout << arr[y][x] << ' ';
      cout << '\n';
   }
}

int main() {
   ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
   cin >> N >> M >> R;
   arr = vector<vector<int>>(N, vector<int>(M));
   for (int y = 0; y < N; ++y)
      for (int x = 0; x < M; ++x)
         cin >> arr[y][x];
   for (int i = 0; i < R; ++i) cin >> op[i];
   solve();
   show();
}

결과

'시뮬레이션' 유형에서 문제를 풀기 전부터 가장 효율적으로 풀이하는 방법부터 고민하는 것이 제 단점입니다.
(i.e. 배열 대입을 어떻게 가장 효율적으로 할 수 있을까, 공간복잡도를 줄일 수 있는 방법이 없을까 등)

앞으로 '시뮬레이션' 유형을 풀 때는 시간 내로 문제를 푸는 것에 집중해서 훈련해야겠습니다.