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

이 포스트는 백준 사이트의 원판 돌리기 문제 풀이입니다.

문제

해결 과정

원판 돌리기 문제는 이전 풀었던 톱니바퀴 문제와 유사한 원리로 풀 수 있습니다.
그러나 톱니바퀴 문제에서는 12시 방향에 있는 원소만 파악하면 풀 수 있었지만
이번 문제는 모든 원소에 접근이 가능하고 회전도 가능해야 합니다.

그래서 이번 문제의 자료구조는 랜덤 액세스가 불가능한 list 대신 Deque을 사용하였습니다.
Deque 은 list 처럼 컨테이너의 시작과 끝에서 삽입, 삭제 연산을 할 수 있고
vector 처럼 랜덤 액세스도 가능합니다.

Queue 는 Deque 에서 랜덤 액세스와 반복자의 수식 연산을 막은 대신
front 부분에서의 삽입, 삭제에서 시간 복잡도가 O(1) 인 자료구조입니다.

[원판을 직선으로 만든 모양]

코드 구현

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

using namespace std;

void input(int& N, int& M, vector<deque<int>>& circle, vector<vector<int>>& order);
void turn_circle(deque<int>& circle, bool counter_clockwise, int cnt);
void cleanup_near_numbers(int N, int M, vector<deque<int>>& circles);
int sum_all_circle_numbers(vector<deque<int>>& circle);

int main() {
    int N, M;
    vector<deque<int>> circle;
    vector<vector<int>> orders;
    input(N, M, circle, orders);
    
    for(auto order : orders) {
        for(int i = 1; i * order[0] <= N; ++i) {
            turn_circle(circle[i * order[0]], order[1], order[2]);
        }
        cleanup_near_numbers(N, M, circle);
    }

    cout << sum_all_circle_numbers(circle);
    
    return 0;
}

void input(int& N, int& M, vector<deque<int>>& circle, vector<vector<int>>& order) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> N >> M >> T;

    circle.assign(N + 1, deque<int>());
    for(int i = 1; i <= N; ++i) {
        for(int j = 0, temp; j < M; ++j) {
            cin >> temp;
            circle[i].push_back(temp);
        }
    }

    order.assign(T, vector<int>());
    for(int i = 0; i < T; ++i) {
        int x, d, k;
        cin >> x >> d >> k;
        order[i] = {x, d, k};
    }
}

void turn_circle(deque<int>& circle, bool counter_clockwise, int cnt) {
    if(false == counter_clockwise) {
        while(cnt--) {
            int temp = circle.back();
            circle.pop_back();
            circle.push_front(temp);
        }
    } else {
        while(cnt--) {
            int temp = circle.front();
            circle.pop_front();
            circle.push_back(temp);
        }
    }
}

void cleanup_near_numbers(int N, int M, vector<deque<int>>& circles) {
    int dir_row[4]{-1, 1, 0, 0};
    int dir_col[4]{0, 0, -1, 1};

    vector<bool> visited(N + 1, false);

    auto next_circle = circles;

    bool find_same_nums = false;
    for(int row = 1; row <= N; ++row) {
        for(int col = 0; col < M; ++col) {
            if(circles[row][col] == 0) continue;
            
            int num_cnt = 0, delete_num_cnt = 0;
            for(int dir = 0; dir < 4; ++dir) {
                int new_row = row + dir_row[dir];
                int new_col = col + dir_col[dir];

                new_row %= N + 1;
                new_col %= M;

                if(new_row < 1 || new_row > N || new_col < 0 || new_col >= M)
                    continue;

                if(0 == circles[new_row][new_col]) {
                    continue;
                }

                num_cnt += 1;
                
                if(circles[row][col] == circles[new_row][new_col]) {
                    visited[new_row] = true;
                    next_circle[new_row][new_col] = 0;
                    find_same_nums = true;
                    delete_num_cnt += 1;
                }
            }

            if(delete_num_cnt >= 1) {
                next_circle[row][col] = 0;
            }
        }
    }

    circles = next_circle;

    if(find_same_nums == false) {
        int sum = 0, cnt = 0;
        for(int row = 1; row <= N; ++row) {
            for(int n : circles[row]) {
                if(n == 0) continue;
                sum += n;
                cnt += 1;
            }
        }
        float avg = (float)sum / cnt;
        for(int row = 1; row <= N; ++row) {
            for(int& n : circles[row]) {
                if(n == 0 || avg == 0) continue;
                else if(n > avg) n -= 1;
                else if(n < avg) n += 1;
            }
        }
    }
}

int sum_all_circle_numbers(vector<deque<int>>& circle) {
    int sum = 0;
    for(auto c : circle) {
        if(c.empty()) continue;
        for(int n : c) {
            sum += n;
        }
    }
    return sum;
}

실행 결과