[ BOJ - 17822번 ] 원판 돌리기 (C++)

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

 

 M개의 숫자를 가지는 N개의 원판을 K번 돌리는 기능을 T번 반복할 때의 최대 연산 횟수를 50x50x50x50라고 생각했을 때,

각 반복에서 아래 조건을 구현하기 위해서 사용할 수 있는 시간복잡도는 최대 O(log n)이다.

1. 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
   1. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
   2. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

따라서, push_back과 push_front를 이용해 원판을 돌리는 기능을 O(1) 시간에 구현할 수 있고 random access에도 O(1)의 시간복잡도를 갖는 deque를 사용하면 문제를 풀 수 있을 것이다.

 

[ 풀이 방법 ]

1. 원판 생성 기능

  - vector를 이용해 N개의 deque를 저장한다.

  - 각 deque는 M개의 원소를 저장한다.

 

2. 원판 회전 기능

  1. x, d, k가 입력되었을 때, x의 배수 index에 있는 원판을 d방향으로 k번 회전하는 기능

    - x의 배수 인덱스를 탐색하기 용이하도록 deque를 저장하는 vector가 인덱스 1번 부터 deque를 저장하도록 구현

    - d가 0인 경우 시계 방향 회전: deque의 마지막 원소를 deque의 가장 앞에 삽입하여 구현

    - d가 1인 경우 빈시계 방향 회전: deque의 첫 번째 원소를 deque의 마지막에 삽입하여 구현

 

3. 회전 후 원판의 M개 위치에 수가 남아있으면 인접한 같은 수를 찾는 기능

  - 찾았다면 해당 위치를 모두 0으로 지워줘야 한다.

  - 없다면 남은 수들의 평균을 구하고, 각 원소들과 비교해 평균보다 작다면 1을 더하고. 크다면 1을 빼준다.

 

구현 방법

  1. sum, cnt, flag 변수를 만들고, 모든 원판을 탐색하며 남아있는 수의 합과 개수, 인접한 같은 수를 찾았는지 여부를 저장한다.

 

  2. 모든 원판을 탐색하며 상하좌우에 현재 위치의 값과 동일한 값이 저장되어 있는지 확인한다.

 

  3. 동일한 값을 찾는다면 해당 위치를 0으로 초기화한다.

 이 때 원본이 아니라 AUX 벡터의 값을 갱신하고 모든 탐색이 끝난 뒤 ORIGIN과 AUX를 swap 해야한다.

 

 4. 동일한 값을 한번도 찾지 못했다면, sum/cnt로 평균을 구하고 원판에 남아있는 수와 비교하여 평균보다 작은 값에는 1을 더하고. 큰 값에는 1을 빼준다.

 이 때 int형의 나눗셈의 경우 자동으로 내림 처리가 되기 때문에 정확한 비교를 위해 실수 자료형을 사용해야 한다.

 

4. 위 과정을 T번 반복한 후 원판에 남아있는 수들의 합을 구하여 출력하는 기능

 

위 기능들을 모두 구현하고, 추가로 원판의 상하좌우를 탐색할 때 vector가 아니라 deque의 범위를 벗어나는 경우인 좌, 우 범위를 벗어나는 경우에는 각각 deque의 마지막 원소, 첫번째 원소를 탐색하도록 수정하여 문제를 해결할 수 있었다.

int nx = i + dirX[dir];
int ny = j + dirY[dir];

if(nx <= 0 || nx > N) continue;
if(ny < 0) ny = M-1;
if(ny >= M) ny = 0;

 

[ 정답 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>

using namespace std;

int N, M, T;
vector<deque<int>> plates;

int dirX[4] = {-1, 1, 0, 0};
int dirY[4] = {0, 0, -1, 1};

void rotateClock(int idx, int k){
    while(k--) {
        int t = plates[idx].back();
        plates[idx].pop_back();
        plates[idx].push_front(t);
    }
}

void rotateReverse(int idx, int k){
    while(k--) {
        int t = plates[idx].front();
        plates[idx].pop_front();
        plates[idx].push_back(t);
    }
}

void check() {
    int sum = 0;
    int flag = true;
    int cnt = 0;
    vector<deque<int>> aux(plates.begin(), plates.end());
    
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j < M; j++) {
            if(plates[i][j] == 0) continue;
            sum += plates[i][j];
            cnt++;
            
            for(int dir = 0; dir < 4; dir++) {
                int nx = i + dirX[dir];
                int ny = j + dirY[dir];

                if(nx <= 0 || nx > N) continue;
                if(ny < 0) ny = M-1;
                if(ny >= M) ny = 0;
                if(plates[i][j] == plates[nx][ny]) {
                    aux[i][j] = 0;
                    aux[nx][ny] = 0;
                    flag = false;
                }
            }
        }
        
    }
    
    if(flag) {
        
        double avg = (double)sum/cnt;
        
        for(int i = 1; i <= N; i++) {
            for(int j = 0; j < M; j++) {
                if(aux[i][j] == 0) continue;
                
                if((double)plates[i][j] < avg) {
                    aux[i][j] += 1;
                } else if ((double)plates[i][j] > avg) {
                    aux[i][j] -= 1;
                }
            }
        }
    }
    
    aux.swap(plates);
    vector<deque<int>>().swap(aux);
}

void solve() {
    
    while(T--) {
        int x, d, k;
        cin >> x >> d >> k;
        void (*rotate[2])(int, int);
        rotate[0] = rotateClock;
        rotate[1] = rotateReverse;
        
        for(int i = x; i <= N; i+=x) {
            rotate[d](i, k);
            
        }
        
        check();
    }
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M >> T;
    plates.resize(N+1, deque<int>());
    
    int t;
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> t;
            plates[i].push_back(t);
        }
    }
    
    solve();
    
    int res = 0;

    for(int i = 1; i <= N; i++) {
        for (int j = 0; j < M; j++) {
            res += plates[i][j];
        }
    }
    cout << res << '\n';
    
    return 0;
}