BOJ 17822번: 원판 돌리기

문제

문제 바로가기> BOJ 17822번: 원판 돌리기

17822번: 원판 돌리기

 

풀이

원판을 2차원 배열로 입력받아서 시뮬레이션을 진행하는 문제였다. 

 

처음에 시간을 절약하기 위해

M/2 < k 인 경우 반대 방향으로 M-k만큼 돌려주었고,

sum, cnt 변수를 전역 변수로 가지고 있는 방식을 이용했다.

 

하지만, 이러한 부분을 빼고

그때그때 sum과 cnt를 가져오는 함수를 만들도록

코드를 변경하면, 코드가 더 깔끔해질 것 같았고,

시간 초과가 발생할 시간 복잡도도 아니어서 다음과 같이 코드를 변경했다!

실제로 돌려봤을 때도 큰 차이가 없었다!

 

주의해야 할 점은 아래 2가지 정도인 것 같다 ㅎㅎ

1. 평균은 double (or float) 형태로 표현!!

2. 인접한 같은 수를 지우는 경우 추가 배열을 이용 (동시에 지우기 때문)

 

#include<iostream>
#define MAX 51
#define EMPTY 0
using namespace std;

struct DATA{int sum, cnt;};

int N, M, T;
int map[MAX][MAX];
int copy_map[MAX][MAX];
int dn[] = {-1, 1, 0, 0};
int dm[] = {0, 0, -1, 1};

void input(){
    cin >> N >> M >> T;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++) cin >> map[i][j];
    }
}

void rotate_clockwise(int x, int k){ // 시계 방향 회전
    for(int n=x; n<=N; n+=x){ // x의 배수 원판 회전
        for(int i=0; i<k; i++){
            int tmp = map[n][M];
            for(int m=M; m>1; m--) map[n][m] = map[n][m-1];
            map[n][1] = tmp;
        }
    }
}

void rotate_counterclockwise(int x, int k){ // 반시계 방향 회전
    for(int n=x; n<=N; n+=x){ // x의 배수 원판 회전
        for(int i=0; i<k; i++){
            int tmp = map[n][1];
            for(int m=1; m<M; m++) map[n][m] = map[n][m+1];
            map[n][M] = tmp;
        }
    }
}

DATA get_sum_cnt(){
    int sum=0, cnt=0;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++) {
            if(map[i][j]==EMPTY) continue;
            sum+=map[i][j]; cnt++;
        }
    } return {sum, cnt};
}

void control_number(){

    for(int i=1; i<=N; i++){ // 동시에 확인하기 때문에!
        for(int j=1; j<=M; j++) copy_map[i][j] = map[i][j];
    }

    bool isEnd = false;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            if(map[i][j] == EMPTY) continue;
            
            int num = map[i][j];
            bool isRemove = false;
            for(int d=0; d<2; d++){ // 상 하 (범위 벗어나면 no)
                int nn = i+dn[d];
                int nm = j+dm[d];
                if(nn<1 || nn>N || nm<1 || nm>M) continue;
                if(map[nn][nm] == num){
                    isRemove = true;
                    copy_map[nn][nm] = EMPTY;
                }
            }
            for(int d=2; d<4; d++){ // 좌 우 (범위 벗어나면 modular)
                int nn = i+dn[d]; if(nn<1) nn+=N; if(nn>N) nn-=N;
                int nm = j+dm[d]; if(nm<1) nm+=M; if(nm>M) nm-=M;
                if(map[nn][nm] == num){
                    isRemove = true;
                    copy_map[nn][nm] = EMPTY;
                }
            }
            if(isRemove) {
                copy_map[i][j] = EMPTY;
                isEnd = true;
            }
        }
    }

    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++) map[i][j] = copy_map[i][j];
    }

    if(isEnd) return; // 인접하면서 같은 수를 모두 지운 경우

    DATA tmp = get_sum_cnt();
    int sum=tmp.sum, cnt=tmp.cnt;
    float mean = sum*1.0/cnt; // 원판에 적힌 수의 평균
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            if(map[i][j]==EMPTY) continue; // 빈칸
            if(map[i][j] < mean) map[i][j]++; // 평균 보다 작은 수
            else if(map[i][j] > mean) map[i][j]--; // 평균보다 큰 수 
        }
    }
}

void solution(){
    int x, d, k;
    while(T--){
        cin >> x >> d >> k;

        // 원판 회전
        if(d==0) rotate_clockwise(x, k);
        else rotate_counterclockwise(x, k);

        // 인접한 수 or 평균 처리
        control_number();
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution();
    cout << get_sum_cnt().sum;
}