[백준/C++] 16927번 배열 돌리기 2

https://www.acmicpc.net/problem/16927

16927번: 배열 돌리기 2

이 문제는 얼핏 보면 아래 소스코드처럼 특정한 규칙을 찾아서 전부 탐색하여 배열을 돌려주면 풀릴 것 같지만,

r의 입력이 최대 10억이므로, 10억번 반복을 하면 O(n)의 시간복잡도를 가질지라도 1초를 넘기게 되므로 시간초과가 뜬다!

​

해결

-> 덱(deque)에 넣어서 돌리자! 양파껍질까듯 바깥의 한 줄씩을 2차원 덱에 차례로 저장해주면 된다!

​

Q1. 몇줄을 껍질까듯 까야하냐?

A1. 행과 열 중 최솟값을 고른 뒤, 나누기 2 했을 때 나오는 값만큼만 까주면 된다! -> 곰곰히 생각해보면 왜 그런지 직관적으로 이해가능..!

​

Q2. 방향이 꺾이는 건 어떻게 하냐?

A2. 방향 벡터를 이용한다. 한 방향으로 쭉 직진하다가 범위를 벗어나게 될 때엔 방향을 바꿔준다.

한바퀴 다 돌렸음에도 계속 방향이 바뀌는 것 역시도 방지해줘야 한다.

​

Q3. 결국 r만큼 반복해야하는 것 아닌가?

A3. 아니다! 예를 들어 최초의 바깥의 한 줄의 길이가 12라고 하자. (4x4 배열은 바깥쪽의 원소의 수가 12이다.)

예를 들어 r이 1~11이면 꼼짝없이 그 값만큼 돌려야하지만, r이 12를 넘는다고 해보자..!

배열을 0번 돌리나, 12번 돌리나 똑같은 값이 나올 것이다. 12시에서 12시간이 지나면 시침은 다시 12를 가리키는 것 처럼!

때문에 r을 i번째 덱의 사이즈로 나누었을 때 나오는 나머지만큼 돌리면 된다!

​

마지막으로, 돌리는 데 성공한 배열을 저장하고 있는 덱을 다시 원래 배열에 저장해주면 된다.

​

※ 방향 벡터의 순서에 따라 아래 코드처럼 약간의 변화가 있을 수 있다

바깥쪽 한 줄을 오른쪽 방향 먼저 저장하느냐, 아래쪽 먼저 저장하느냐의 차이이다.

dq[i].push_back(dq[i].front());
dq[i].pop_front();

dq[i].push_front(dq[i].back());
dq[i].pop_back();

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cstring>
#include <string>
#include <queue>
#include <functional>
#include <complex>
#include <cmath>
#include <unordered_map>
#include <map>
typedef long long ll;
using namespace std;

int n,m;
ll r;
int arr[301][301];
bool visited[301][301];
// 오른쪽 아래쪽 왼쪽 위쪽 순서
int dx[]={0,1,0,-1};
int dy[] ={1,0,-1,0};
deque<int> dq[301];

bool changeDir(int x, int y, int d){
    int nx = x + dx[d];
    int ny = y + dy[d];
    if (nx > n || nx < 1 || ny > m || ny < 1) return true;
    if (visited[nx][ny]) return true;
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m >> r;
    for(int i=1; i<=n;i++){
        for(int j=1; j<=m;j++){
            cin >> arr[i][j];
        }
    }
    int cnt = min(n, m) / 2;
    for (int i = 1; i <= cnt; i++) {
        int x = i, y = i, d = 0;
        while(true) {
            if(visited[x][y]) break;
            visited[x][y] = true;
            dq[i].push_back(arr[x][y]);
            if(changeDir(x,y,d)) d++;
            x= x + dx[d];
            y = y + dy[d];
            if(d==4) break;
        }
    }

    // rolling
    for (int i = 1; i <= cnt; i++) {
        int k = r % dq[i].size(); // 굳이 r만큼 돌릴 필요 x
        while (k--) {
            dq[i].push_back(dq[i].front());
            dq[i].pop_front();
        }
    }
    memset(visited,false,sizeof(visited));
    for (int i = 1; i <= cnt; i++) {
        int x = i, y = i, d = 0,k=0;
        while(true) {
            if(visited[x][y]) break;
            visited[x][y] = true;
            arr[x][y] = dq[i][k++];
            if(changeDir(x,y,d)) d++;
            x= x + dx[d];
            y = y + dy[d];
            if(d==4) break;
        }
    }

    for(int i=1; i<=n;i++){
        for(int j=1; j<=m;j++){
            cout << arr[i][j] << ' ';
        }
        cout << '\n';
    }
}

아래는 시간초과난 코드 ㅎㅎ

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cstring>
#include <string>
#include <queue>
#include <functional>
#include <complex>
#include <cmath>
#include <unordered_map>
#include <map>
typedef long long ll;
using namespace std;

int n,m,r;
int arr[301][301];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m >> r;
    for(int i=1; i<=n;i++){
        for(int j=1; j<=m;j++){
            cin >> arr[i][j];
        }
    }

    while(r--) {
        int d=0,depth=1;
        int cnt = min(n, m) / 2;
        while (cnt--) {
            int tmp = arr[n - d][depth];

            // 왼쪽
            for (int x = n - d; x > depth; x--) {
                arr[x][depth] = arr[x - 1][depth];
            }
            // 위쪽
            for (int y = depth; y < m - d; y++) {
                arr[depth][y] = arr[depth][y + 1];
            }
            // 오른쪽
            for (int x = depth; x < n - d; x++) {
                arr[x][m - d] = arr[x + 1][m - d];
            }
            // 아래쪽
            for (int y = m - d; y > depth; y--) {
                arr[n - d][y] = arr[n - d][y - 1];
                if (y == depth+1) {
                    arr[n - d][y] = tmp;
                }
            }
            depth++;
            d++;
        }
    }
    for(int i=1; i<=n;i++){
        for(int j=1; j<=m;j++){
            cout << arr[i][j] << ' ';
        }
        cout << '\n';
    }
}