[백준] 16926번 : 배열 돌리기 1 (C++)

16926번 : 배열 돌리기 1

---

문제)

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.

A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5]
   ↓                                       ↑
A[2][1]   A[2][2] ← A[2][3] ← A[2][4]   A[2][5]
   ↓         ↓                   ↑         ↑
A[3][1]   A[3][2] → A[3][3] → A[3][4]   A[3][5]
   ↓                                       ↑
A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5]

예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.

1 2 3 4       2 3 4 8       3 4 8 6
5 6 7 8       1 7 7 6       2 7 8 2
9 8 7 6   →   5 6 8 2   →   1 7 6 3
5 4 3 2       9 5 4 3       5 9 5 4
 <시작>         <회전1>        <회전2>

배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.

 

 

 

입력 :

첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

 

 

 

출력 :

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

 

 

 

 

 

 

풀이)

 

// 16926. 배열 돌리기 1
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int n, m, r;
 
vector<vector<int>> vec;
 
// vector<int>로 사용했으나,
// 속도를 좀 높여보고자 struct를 사용해봤음
struct node
{
    int a;
    int b;
    int prev;
    int direct;
};
 
// 배열을 출력하는 함수
void print()
{
    for (auto ele : vec)
    {
        for (auto e : ele)
        {
            cout << e << " ";
        }
        cout << '\n';
    }
}
 
// 배열을 순환시키는 함수
void rotation(int a, int b, int prev)
{
    // queue를 이용하여 순환시켜주었음
    queue<node> q;
    // 4번째 인자는 방향을 설정함
    q.push({a, b, prev, 0});
 
    int dx, dy;
    while (!q.empty())
    {
        int x = q.front().a;
        int y = q.front().b;
        int num = q.front().prev;
        int drt = q.front().direct;
        q.pop();
        
        if (drt == 0) dx = 1, dy = 0;    // 하
        else if (drt == 1) dx = 0, dy = 1;    // 우
        else if (drt == 2) dx = -1, dy = 0;    // 상
        else if (drt == 3) dx = 0, dy = -1;    // 좌
 
        int nx = x + dx;
        int ny = y + dy;
 
        // 하단으로 이동하다 한계점을 만났을 때
        if (nx >= n - a)
        {
            nx += -1;
            ny++;
            drt = 1;
        }
        else if (ny >= m - b)
        {
            nx -= 1;
            ny--;
            drt = 2;
        }
        else if (nx < a)
        {
            nx++;
            ny--;
            drt = 3;
        }
        else if (ny < b) return;
 
        q.push({nx, ny, vec[nx][ny], drt});
        vec[nx][ny] = num;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m >> r;
 
    vec.resize(n, vector<int>(m, 0));
    for (auto& ele : vec) for (auto& e : ele) cin >> e;
 
    for (int i = 0; i < min(n / 2, m / 2); i++)
    {
        for (int j = i; j < i + 1; j++)
        {
            // r회전 최적화
            int a = r % ((n - (i * 2) - 1) * 2 + (m - (j * 2) - 1) * 2);
            for (int t = 0; t < a; t++)
            {
                rotation(i, j, vec[i][j]);
            }
        }
    }
 
    print();
 
    return 0;
}
 
 

---

출처 : https://www.acmicpc.net/problem/16926 

16926번: 배열 돌리기 1