[백준] 17822 원판 돌리기

문제 링크 : www.acmicpc.net/problem/17822

17822번: 원판 돌리기

문제 유형

구현, 시뮬레이션

 

이런 시뮬레이션 형태의 구현 문제는, 어떠한 동작을 수행하는 매개체를 클래스 형태로 구현하면 비교적 깔끔하게 구현이 가능하다.

이 문제에서는 각 원판을 disk라는 클래스로 정의하고, 이 클래스 내부에 회전 및 인접 값 제거 메소드를 구현했다.

각 원판의 숫자들은 deque 형태로 저장해 회전 구현을 쉽게 할 수 있도록 했고, 인접 값 참조를 쉽게 할 수 있도록 상위, 하위 디스크를 링크 형태로 이어주었다.

인접 값 참조는 각 원판의 숫자마다 DFS 형태로 구현해 한 번의 참조로 최대한 많은 동일 값들을 제거할 수 있도록 하였다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
 
using namespace std;
typedef pair<int, int> p;
 
int n, m, t;
bool eliminated_flag = false;
 
class disk {
private:
    deque<int> dque;
    disk* upper;    //한 단계 높은 디스크
    disk* lower;        //한 단계 낮은 디스크
    int valid = 0;    //유효 숫자의 수
    
 
public:
    void init_dque(int* list) {
        for (int i = 0; i < m; i++) dque.push_back(*(list + i));
        valid = m;
    }
 
    void set_upper(disk* up) { upper = up; }
    void set_lower(disk* low) { lower = low; }
 
    void rotate(int dir, int amount) {
        if (dir) {
            //반시계 방향
            for (int i = 0; i < amount; i++) {
                int temp = dque.front();
                dque.pop_front();
                dque.push_back(temp);
            }
        }
        else {
            //시계 방향
            for (int i = 0; i < amount; i++) {
                int temp = dque.back();
                dque.pop_back();
                dque.push_front(temp);
            }
        }
    }
 
    int get_val(int pos) { return dque[pos]; }
 
    int get_sum() {
        int ret = 0;
        for (int i = 0; i < m; i++) ret += dque[i];
        return ret;
    }
 
    int get_valid() { return valid; }
 
    void eliminate(int pos, bool adj) {
        //현재 원판의 pos번째 수와 인접한 같은 모든 수를 제거한다. (DFS)
        bool adj_exist = adj;
        if (dque[pos] == 0) return;
 
        int temp = dque[pos];
        dque[pos] = 0;
 
        int next = pos == m - 1 ? 0 : pos + 1;
        int prev = pos == 0 ? m - 1 : pos - 1;
 
        //동일 원판 양 옆에서 인접 제거
        if (temp == dque[next]) { adj_exist = true; eliminate(next, true); }
        if (temp == dque[prev]) { adj_exist = true; eliminate(prev, true); }
 
        //위, 아래 원판에서 인접 제거
        if (upper != NULL && temp == upper->get_val(pos))
        { adj_exist = true; upper->eliminate(pos, true); }
 
        if (lower != NULL && temp == lower->get_val(pos))
        { adj_exist = true; lower->eliminate(pos, true); }
 
        if (adj_exist) { valid -= 1; eliminated_flag = true; }
        else dque[pos] = temp;
    }
 
    void modify_dque(double avgval) {
        for (int i = 0; i < m; i++) {
            if (dque[i] == 0) continue;
            if ((double)dque[i] > avgval) dque[i] -= 1;
            else if ((double)dque[i] < avgval) dque[i] += 1;
        }
    }
};
 
disk disks[51];
 
void eliminate_val() {
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            disks[i].eliminate(j, false);
        }
    }
}
 
double average() {
    int valid_cnt = 0, val_sum = 0;
    for (int i = 1; i <= n; i++) {
        valid_cnt += disks[i].get_valid();
        val_sum += disks[i].get_sum();
    }
    return (double)val_sum / valid_cnt;
}
 
void init() {
    cin >> n >> m >> t;
    for (int i = 1; i <= n; i++) {
        int val_arr[51];
 
        for (int i = 0; i < m; i++) cin >> val_arr[i];
        disks[i].init_dque(val_arr);
 
        if (i > 1) disks[i].set_lower(&disks[i - 1]);
        if (i < n) disks[i].set_upper(&disks[i + 1]);
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    int x, d, k;
    init();
    for (int i = 0; i < t; i++) {
        cin >> x >> d >> k;
 
        for (int j = x; j <= n; j += x) {
            //x의 배수 번호인 원판에 대해, 회전 수행
            disks[j].rotate(d, k);
        }
 
        //원판 내에 존재하는 인접 수들을 모두 제거
        eliminated_flag = false;
        eliminate_val();
 
        if (!eliminated_flag) {
            double avgval = average();
            for (int i = 1; i <= n; i++) disks[i].modify_dque(avgval);
        }
    }
 
    int answer = 0;
    for (int i = 1; i <= n; i++) answer += disks[i].get_sum();
    printf("%d\n", answer);
 
    return 0;
}