[Algorithm] 백준 17822 - 원판 돌리기

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

17822번: 원판 돌리기

문제

반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다.

• (i, 1)은 (i, 2), (i, M)과 인접하다.
• (i, M)은 (i, M-1), (i, 1)과 인접하다.
• (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
• (1, j)는 (2, j)와 인접하다.
• (N, j)는 (N-1, j)와 인접하다.
• (i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)

아래 그림은 N = 3, M = 4인 경우이다.

원판의 회전은 독립적으로 이루어진다. 2번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키기 전과 일치해야 한다.

다음 그림은 원판을 회전시킨 예시이다.

1번 원판을 시계 방향으로 1칸 회전	2, 3번 원판을 반시계 방향으로 3칸 회전	1, 3번 원판을 시계 방향으로 2칸 회전
1번 원판을 시계 방향으로 1칸 회전	2, 3번 원판을 반시계 방향으로 3칸 회전	1, 3번 원판을 시계 방향으로 2칸 회전

원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.

1. 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
2. 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
   1. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
   2. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.

 

생각해 보기

1. 진행 순서는 입력 -> 회전 -> 동일한 값 체크 -> 없으면 평균 비교 이다.
2. 원소가 없는 경우와 평균을 편하게 구하기 위해 입력 받을때 sz(원판에 남은 원소의 갯수)와 sum(원판에 남은 원소의 총합)을 구하면서 진행하였다.
3. 회전의 경우 deque를 사용하여 시계 방향 회전은 맨 뒤 원소를 맨 앞에 push한 뒤 pop, 반시계 방향 회전은 맨 앞 원소를 맨 뒤에 push한 뒤 pop하는 방식으로 사용
4. 원판과 원소의 시작점을 0부터 잡았으므로 0번이나 N-1번 원판의 N축 이동에서의 비교를 하는경우 범위를 넘어가면 continue로 넘겨주고, 같은 원판의 경우 한칸 이동시키고 M을 더해준 뒤 M의 나머지 연산을 통해 역방향과 순방향 원소의 체크를 진행하였다.
   • M = 0번 칸 체크시 0 -1 = -1번칸과 0 + 1 = 1을 체크해야한다. 마지막 칸의 인덱스는 M - 1 이므로 양방향에 M을 더해주면 M - 1,  M + 1이 되고 이를 M의 나머지를 구하게 되면 M - 1, 1이 남게되어 양방향 체크가 가능해진다.
   • M = M - 1번 칸 체크시 M - 2, M번칸 체크가 되고 동일한 방법으로 진행하면 M + M - 2, M + M이 되며 나머지는 M - 2, 0이 되어 양방향 체크가 가능해진다.
5. 4번에서 동일한 원소가 있는 경우 바로 제거를 하게 되면 1칸만 연속이 아닌 3칸이상 연속 되어있는 경우를 확인할 수 없게 된다. (0,1), (1,1), (2,1)과 같은 경우를 제외하기 위해 vector에 같은 원소가 있으면 저장해논 뒤에 마지막에 제거를 진행한다.
6. 만약 vector의 사이즈가 0인 경우 제거된 원소가 없으므로 평균제거를 진행한다.
7. 3번으로 이동하여 원소의 갯수를 체크하고 다시 진행하거나 종료한다.

 

코드

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

using namespace std;

int my[4]={0,1,0,-1};
int mx[4]={1,0,-1,0};
deque<int> arr[55];
int N,M,T,sum,sz;

void turn_cw(int x, int k){
    for(int i=1;i*x<=N;i++){
        int t=k,idx=i*x-1;
        while(t--){
            arr[idx].push_front(arr[idx].back());
            arr[idx].pop_back();
        }
    }
}

void turn_ccw(int x, int k){
    for(int i=1;i*x<=N;i++){
        int t=k,idx=i*x-1;
        while(t--){
            arr[idx].push_back(arr[idx].front());
            arr[idx].pop_front();
        }
    }
}

bool same_element(){
    vector<pair<int,int> > s;

    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(arr[i][j]==-1)
                continue;
            for(int m=0;m<4;m++){
                int ny=i+my[m];
                int nx=(j+mx[m]+M)%M;

                if(ny<0||ny>=N)
                    continue;

                if(arr[ny][nx]==arr[i][j]){
                    s.push_back({i,j});
                    break;
                }
            }
        }
    }

    int ssz=s.size();
    sz-=ssz;

    for(int i=0;i<ssz;i++){
        int y=s[i].first;
        int x=s[i].second;

        sum-=arr[y][x];
        arr[y][x]=-1;
    }

    return s.empty();
}

void avg(){
    double av=(double)sum/sz;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(arr[i][j]==-1)
                continue;
            if((double)arr[i][j]>av){
                arr[i][j]--;
                sum--;
            }
            else if((double)arr[i][j]<av){
                arr[i][j]++;
                sum++;
            }
        }
    }
}

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

    cin>>N>>M>>T;

    int tmp;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin>>tmp;
            arr[i].push_back(tmp);
            sum+=tmp;
        }
    }
    sz=N*M;
        

    int x,d,k;
    while(T--&&sz){
        cin>>x>>d>>k;
        if(d==0)
            turn_cw(x,k);
        else
            turn_ccw(x,k);
        if(same_element())
            avg();
    }

    cout<<sum<<'\n';

    return 0;
}

 

 

알고리즘 분류

• 구현
• 시뮬레이션