백준 17822번 : 원판 돌리기 - 구현, 시뮬레이션 C++

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

17822번: 원판 돌리기

1.문제설명

1. 회전하는 함수를 구현한다.

2. 각 원판을 회전 후 인접점을 검사하여 같은 값을 가진 좌표가 있을 경우 해당 지점들은 모두 없앤다.

3. 인접점이 없을 경우 평균을 구해 평균보다 작은 값은 +1 평균보다 큰 값은 모두 -1을 해준다.

 

 

 

1. 회전하는 함수는 deque를 이용하면 쉽게 구현할 수 있다.

2. 인접지점을 검사하는 기능을 구현하는 것이 이 문제의 핵심인데,

규칙을 잘 발견하면 깔끔하게 구할 수 있다.

 

인접지점 중 현재 점과 같은 값을 가진 지점이 존재하는지 검사를 해야하는데

이게 현재 지점이 어떤 점위에 있느냐에 따라 케이스가 나뉘어져

복잡한 if문을 사용해서 풀 수도 있다.

 

그런데 현재 원판이 1번, 2번, ... N번 원판 까지 있으면

가상의 0번 원판, N+1번 원판이 존재한다고 생각하고

해당 원판에 존재하는 수를 모두 0으로 두면

조건을 좀 더 간단하게 만들 수 있다.

 

이런식으로 문제를 풀 수 있는 이유는

문제 조건에서 원판 위의 숫자는 자연수로만 두기 때문에

0과 비교하면 무조건 다른 값을 가진 것으로 나타난다.

 

빨간색 0이 임의로 추가해준 지점이고

파란색 동그라미의 2와 3은 해당 지점에서 인접 지점을 검사할 때

검사할 지점들을 나타낸다

 

이런식으로 구현하면 1번 원판과 N번 원판을 굳이 따로 케이스를 분류하지 않고 풀어도 된다.

 

 

---

2.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

int N, M, T;
int arr[52][52];

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void Input();
double getMeans();
void plusMinus();


//row를 k번 돌린다
void rotateClock(int row, int k) {
    deque<int> dq;

    for (int i = 1; i <= M; i++) {
        dq.push_back(arr[row][i]);
    }

    for (int i = 0; i < k; i++) {
        dq.push_front(dq.back());
        dq.pop_back();
    }

    for (int i = 1; i <= M; i++) {
        arr[row][i] = dq.front();
        dq.pop_front();
    }
}

void rotate(int x, int d, int k) {
    for (int i = 1; i <= N; i++) {
        if (i % x == 0) {
            if (d == 0) {
                rotateClock(i, k);
            } else {
                rotateClock(i, M - k);
            }
        }
    }
}

void getAdjacentPoint() {
    vector<pair<int, int> > points;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (arr[i][j] == 0) continue;
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];

                if (ny > M) ny = 1;
                else if (ny < 1) ny = M;

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

    if (points.size() > 0) {
        for (auto p: points) {
            arr[p.first][p.second] = 0;
        }
    } else {
        plusMinus();
    }
}


double getMeans() {
    int cnt = 0;
    double sum = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (arr[i][j] > 0) cnt++;
            sum += arr[i][j];
        }
    }

    if (cnt == 0) return 0;
    else return sum / cnt;
}

void plusMinus() {
    double standard = getMeans();

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (arr[i][j] == 0) continue;

            if (arr[i][j] > standard) {
                arr[i][j]--;
            } else if (arr[i][j] < standard) {
                arr[i][j]++;
            }
        }
    }
}


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

    Input();

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

    cout << ans << '\n';
}


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

    for (int t = 0; t < T; t++) {
        int x, d, k;
        cin >> x >> d >> k;

        rotate(x, d, k);
        getAdjacentPoint();
    }
}