(백준 c++)17822 원판 돌리기

www.acmicpc.net/problem/17822

17822번: 원판 돌리기

 

 

원판은 덱, 수의 위치(i, j)는 큐로 관리하였다.

 

우선 N개의 덱을 저장하는 벡터 disk.

M개의 수를 임시 덱에 저장하고 disk에 넣어주도록 한다.

이때, remain 변수를 늘려주었다.

(remain 변수는 원판에서 0이 아닌 수, 제거되지 않은 수다)

 

T번 반복하자.

x, d, k를 순서대로 받아온다.

그리고 x의 배수에 해당하는 원판을 d의 방향으로 k번 돌려주도록 한다.

각 원판은 덱이기 때문에 앞뒤로 pop, push가 자유롭다.

(x의 배수로 안해서 처음에 애먹었다... 주의하도록 하자.)

 

이제 원판의 수를 하나하나 접근해서 인접한 범위에서 같은 수를 제거한다.

주의점은 원판의 숫자에 접근하는 인덱스가 범위를 벗어나지 않도록 if문으로 조절하도록 하자..!

인접한 수가 현재 위치의 수와 같다면 인접한 수의 인덱스를 큐에 넣어준다.

그리고 한번이라도 같다면 isSame 변수를 true로 바꿔준다.

(isSame == true면 현재 위치의 수를 0으로 바꾼다.)

 

큐가 비어있으면 평균을 구해 수를 다시 재정의 해야한다.

원판을 돌아 총합을 구한 뒤 remain 변수로 나눠주도록 한다.

float나 double형으로 평균값을 저장(중요!).

그리고 평균값보다 원판의 수가 크다면 -1, 작다면 +1, 같다면 그대로 둔다.

 

큐가 비어있지 않다면 원판의 인덱스를 꺼내 해당 위치에 있는 수를 0으로 바꿔주고, remain--을 실행한다.

만약 이미 0으로 바뀌어 있다면 remain은 그대로 둔다.

 

while문이 끝나면 원판의 수를 더해 값을 출력한다.

#include <iostream>
#include <vector>
#include <deque>
#include <queue>

using namespace std;

int main(void){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
    int N, M, T, ans = 0, remain = 0;

    cin >> N >> M >> T;
    
    vector<deque<int>> disk;

    for(int i = 0; i < N; i++){
        deque<int> dq;

        for(int j = 0; j < M; j++){
            int n;
            
            cin >> n;
            
            dq.push_back(n);
            remain++;
        }
        disk.push_back(dq);
    }

    while(T--){
        int x, d, k;
        //인접한 수의 위치를 저장하는 큐. 한꺼번에 0으로 만들어준다.
        queue<pair<int, int>> q;

        cin >> x >> d >> k;

        for(int i = x; i <= N; i += x){
            deque<int> &dq = disk[i - 1];
            int tmp = k;
            
            if(d){
                //반시계방향으로 원판 돌리기
                while(tmp--){
                    dq.push_back(dq.front());
                    dq.pop_front();
                }
            }
            else{
                //시계방향으로 원판 돌리기
                while(tmp--){
                    dq.push_front(dq.back());
                    dq.pop_back();
                }
            }
        }
        
        //인접한 수의 위치 큐에 넣기
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(disk[i][j] == 0){
                    continue;
                }

                int current = disk[i][j];
                bool isSame = false;

                if(j == 0){
                    if(current == disk[i][j + 1]){
                        q.push({i, j + 1});
                        isSame = true;
                    }

                    if(current == disk[i][M - 1]){
                        q.push({i, M - 1});
                        isSame = true;
                    }

                    if(i < N - 1 && current == disk[i + 1][j]){
                        q.push({i + 1, j});
                        isSame = true;
                    }
                }
                else if(j == M - 1){
                    if(current == disk[i][0]){
                        q.push({i, 0});
                        isSame = true;
                    }
                    
                    if(current == disk[i][j - 1]){
                        q.push({i, j - 1});
                        isSame = true;
                    }

                    if(i < N - 1 && current == disk[i + 1][j]){
                        q.push({i + 1, j});
                        isSame = true;
                    }
                }
                else{
                    if(current == disk[i][j + 1]){
                        q.push({i, j + 1});
                        isSame = true;
                    }

                    if(current == disk[i][j - 1]){
                        q.push({i, j - 1});
                        isSame = true;
                    }

                    if(i < N - 1 && current == disk[i + 1][j]){
                        q.push({i + 1, j});
                        isSame = true;
                    }
                }

                if(isSame){
                    disk[i][j] = 0;
                    remain--;
                }
            }
        }

        if(q.empty()){
            int num = 0;

            for(int i = 0; i < N; i++){
                for(int j = 0; j < M; j++){
                    num += disk[i][j];
                }
            }

            double avg = (double)num / (double)remain;
            remain = 0;

            for(int i = 0; i < N; i++){
                for(int j = 0; j < M; j++){
                    if(disk[i][j] == 0){
                        continue;
                    }
                    
                    if(disk[i][j] > avg){
                        disk[i][j]--;
                    }
                    else if(disk[i][j] < avg){
                        disk[i][j]++;
                    }
                    remain++;
                }
            }
        }
        else{
            while(!q.empty()){
                int i = q.front().first;
                int j = q.front().second;

                if(disk[i][j] != 0){
                    remain--;
                }
                disk[i][j] = 0;
                q.pop();
            }
        }
    }

    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            ans += disk[i][j];
        }
    }

    cout << ans;

    return 0;
}