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

Embedded June·2021년 4월 6일
0

알고리즘::백준

목록 보기
88/109

문제

문제접근

문제 이해

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

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

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

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

1번 연산 - 상하 반전

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

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

    • 만일 NN번째 행까지 반전을 계속한다면 다시 원상복귀 되겠죠?
  • 서로 대칭된 위치에 있는 두 행을 교환하는 방법은 두 가지가 있습니다.

    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/2N / 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)로 옮겨집니다.
    • 만일 이해가 안되신다면 꼭 손으로 그려보시면서 이해하시길 바랍니다.
  • 주의해야할 점은 회전 시 NM이 바뀌어야 한다는 점입니다.
    • 예를 들어 3×53 \times 5 배열은 회전 시 5×35 \times 3 배열로 바뀝니다.

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

  • 이번에는 그룹에 대해 좌우 회전을 수행합니다.
  • 그룹에 대한 좌우 회전은 3, 4번 연산과 달리 NM이 바뀌지 않습니다.
  • 그룹에 대한 범위를 정의해야 합니다.
    • 1번 그룹: 0y<N/20 \leq y < N/2, 0x<M/20 \leq x < M / 2
    • 2번 그룹: 0y<N/20 \leq y < N/2, M/2x<MM/2 \leq x < M
    • 3번 그룹: N/2y<NN/2 \leq y < N, M/2x<MM/2 \leq x < M
    • 4번 그룹: N/2y<NN/2 \leq y < N, 0x<M/20 \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. 배열 대입을 어떻게 가장 효율적으로 할 수 있을까, 공간복잡도를 줄일 수 있는 방법이 없을까 등)

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

profile
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.

0개의 댓글