[ 백준 ] 16926 / 배열 돌리기 1

金弘均·2021년 9월 14일
0

Baekjoon Online Judge

목록 보기
12/228
post-thumbnail

# Appreciation

/*
 * Problem :: 16926 / 배열 돌리기 1
 *
 * Kind :: Simulation
 *
 * Insight
 * - abcd  -> bcde  -> cdef  -> ...
 *   j..e     a..f     b..g
 *   ihgf     jihg     ajih
 *   + 설명대로 주어진 배열을
 *     반시계 방향으로 한칸씩 여러번 돌리면 되는데
 *     뭔가 비효율적인것 같다
 *     한번에 할 수 없을려나?
 *     # 현재 반시계 방향으로 한칸씩 돌릴 때
 *       이동되기 전 칸들의 좌표와 값들을 차례대로 저장한 후
 *       그 값들의 위치를 적당히 옮겨주면
 *       한번에 여러번 돌리는 것과 같지 않을까?
 *       -> 2x2 배열
 *          1 2
 *          3 4
 *          를 5번 회전시킨다면
 *          좌표 / (1,1) (2,1) (2,2) (1,2)
 *           값 /   1     3     4     2
 *          => [1, 3, 4, 2] R = 0
 *             [2, 1, 3, 4] R = 1
 *             [4, 2, 1, 3] R = 2
 *             [3, 4, 2, 1] R = 3
 *             [1, 3, 4, 2] R = 4
 *             [2, 1, 3, 4] R = 5
 *             이후 다시 (1,1) (2,1) (2,2) (1,2) 에
 *             위의 값들을 순서대로 넣어준다면
 *             5번 회전시킨것과 같다!
 *
 * Point
 * - Zero-based Numbering
 *   + 왼쪽 맨 위 좌표는 문제에선 (1,1) 이지만
 *     편의상 코드에서는 (0,0) 으로 다루어주었다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <deque>

using namespace std;

#define endl '\n'

// Set up : Global Variables
struct Point {int y, x; };

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N, M, R;
    cin >> N >> M >> R;
    int A[N][M];
    for (int i=0; i<N; i++)
        for (int j=0; j<M; j++)
            cin >> A[i][j];

    // Process
    for (int i=0; i<min(N,M)/2; i++) {
        /* (i,i) 에서 회전시작 */
        int n = N-2*i, m = M-2*i; /* 현재 회전의 세로길이, 가로길이 */
        int a = 2*n + 2*m - 4; /* 현재 회전하는 칸들의 개수 */
        int r = R % a; /* 유효한 회전 횟수 */
        int lly = i+n-1, llx = i; /* 현재 회전하는 칸들의 맨 왼쪽 아래 (y,x) 좌표 */
        int ury = i, urx = i+m-1; /* 현재 회전하는 칸들의 맨 오른쪽 위 (y,x) 좌표 */
        deque<Point> P; /* 현재 회전하는 칸들의 좌표가 담긴 Deque */
        deque<int> V; /* 현재 회전하는 칸들의 값이 담긴 Deque */
        /* (i,i) 부터 아래쪽, 오른쪽, 위쪽, 왼쪽 순서로 칸들을 순회 */
        for (int y=ury; y<lly; y++) /* 초기 배열에서 아래쪽 방향으로 이동하는 칸들 */
            P.push_back({y, llx}), V.push_back(A[y][llx]);
        for (int x=llx; x<urx; x++) /* 초기 배열에서 오른쪽 방향으로 이동하는 칸들 */
            P.push_back({lly, x}), V.push_back(A[lly][x]);
        for (int y=lly; y>ury; y--) /* 초기 배열에서 위쪽 방향으로 이동하는 칸들 */
            P.push_back({y, urx}), V.push_back(A[y][urx]);
        for (int x=urx; x>llx; x--) /* 초기 배열에서 왼쪽 방향으로 이동하는 칸들 */
            P.push_back({ury, x}), V.push_back(A[ury][x]);
        for (int j=0; j<r; j++) /* r번 회전 */
            V.push_front(V.back()), V.pop_back();
        for (int j=0; j<a; j++) { /* 회전한 값들을 위에서 순회한 순서대로 채워줌 */
            auto [y, x] = P.front(); P.pop_front();
            int v = V.front(); V.pop_front();
            A[y][x] = v;
        }
    }

    // Control : Output
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            cout << A[i][j] << ' ';
        } cout << endl;
    }
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글