[백준] 17822 원판 돌리기

17822번: 원판 돌리기

 

www.acmicpc.net

풀이

시뮬레이션 문제라 문제에 나와있는데로 구현하면 해결할 수 있다. 크게 3가지 부분으로 나눠진다.

1. 원판 돌리기
2. 인접한 숫자 제거하기
3. 제거할 숫자가 없으면 평균값과 비교하여 숫자 변경

각 부분별로 설명하겠다.

우선 원판을 돌리기에 앞서 원판을 데이터로 표현해야하는데 2차원 배열 c[i][j]를 이용하여 표현하였다. 가장 안쪽 원판부터 바깥쪽 원판 순서로 i값이 증가하고 각 원판은 12시 방향을 기준으로 시계방향으로 갈수록 j값이 증가하도록 표현하였다.

이제 원판을 회전시켜볼 차례이다. 원판은 시계방향, 반시계방향 모두 회전할 수 있다. deque는 앞, 뒤로 push하고 pop 할 수 있으므로 deque를 사용하여 구현하였다. deque에 한 원판의 값을 모두 저장한 다음, 방향에 맞춰 숫자를 pop하고 push하여 회전을 구현하였다. 그리고 x의 배수 번호 원판을 모두 회전해야하므로 제귀적으로 호출하여 배수를 모두 회전시킬 수 있도록 구현하였다.

이제 인접한 부분을 확인하여 제거할 차례이다. 반복문을 돌면서 인접한 것을 확인하면 된다. 이차원 배열 adj[n][m]을 선언하여 인접한 부분을 체크하고, 모든 체크가 끝나면 한번에 지워주는 방식으로 구현하였다.

우선 같은 원판 내의 인접한 부분을 검사한다.
이 때 m-1까지만 검사하고 c[i][m-1]과 c[i][0]을 검사함으로써 코드의 길이를 줄일 수 있다.

for (int i = 0; i < n; i++) {
        for (int j = 0; j < m-1; j++) {
            if (c[i][j] == 0) continue;
            // 현재 위치와 다음 위치만 검사
            if (c[i][j] == c[i][j + 1]) {
                adj[i][j] = true;
                adj[i][j + 1] = true;
            }
        }
        if (c[i][m-1] == 0) continue;
        // 배열 양 끝 검사
        if (c[i][0] == c[i][m - 1]) {
            adj[i][0] = true;
            adj[i][m - 1] = true;
        }
    }

다음은 다른 원판이지만 같은 위치에 인접한지 검사한다. 이 때 n-1까지만 검사해주면 된다.

for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m; j++) {
            if (c[i][j] == 0) continue;
            if (c[i][j] == c[i + 1][j]) {
                adj[i][j] = true;
                adj[i + 1][j] = true;
            }
        }
    }

이제 모든 인접한 부분을 검사했으므로 체크한 부분의 숫자를 제거한다. 이 때, 제거할 부분이 없는 경우 평균값으로 기준으로 원판의 숫자를 변경해야하므로 0이 아닌 부분의 개수를 세어주고, 전체 합계를 구해준다.

for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (adj[i][j]) {
                c[i][j] = 0;
                chk++;
            }
            if (c[i][j] != 0) non_zero++;
            ans += c[i][j];
        }
}

마지막으로 제거하지 않는 경우 원판의 값을 변경해야하는 부분을 살펴보자. 평균값을 정확히 내야하므로 double자료형을 선언하여 평균을 계산하였다.

// 평균을 정확하게 하기 위해서 double 자료형 사용
    double tmp = ans;
    // 제거할 숫자가 없는 경우 평균값을 구해서 증가시킴
    if (chk == 0) {
        ans = 0;
        tmp /= non_zero;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (c[i][j] == 0) continue;
                if (c[i][j] > tmp) c[i][j]--;
                else if (c[i][j] < tmp) c[i][j]++;
                ans += c[i][j];
            }
        }
    }

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m, t, ans;
vector<vector<int>> c;

void print() {
    cout << '\n';
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << c[i][j] << ' ';
        cout << '\n';
    }
}

// 원판 회전
void spin(int idx, int x, int dir, int k) {
    if (idx - 1 >= n) return;
    int tmp = k;
    deque<int> q;
    for (int i = 0; i < m; i++)
        q.push_back(c[idx - 1][i]);

    while (tmp--) {
        if (dir == 0) {
            q.push_front(q.back());
            q.pop_back();
        }
        else {
            q.push_back(q.front());
            q.pop_front();
        }
    }

    for (int i = 0; i < m; i++) {
        c[idx - 1][i] = q.front();
        q.pop_front();
    }
    spin(idx + x, x, dir, k);
}

// 인접한 숫자 제거
void remove() {
    vector<vector<bool>> adj(n, vector<bool>(m, false));
    ans = 0;
    int chk = 0;
    int non_zero = 0;

    // 같은 원판에 인접한 숫자들 검사
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m-1; j++) {
            if (c[i][j] == 0) continue;
            if (c[i][j] == c[i][j + 1]) {
                adj[i][j] = true;
                adj[i][j + 1] = true;
            }
        }
        if (c[i][m-1] == 0) continue;
        if (c[i][0] == c[i][m - 1]) {
            adj[i][0] = true;
            adj[i][m - 1] = true;
        }
    }

    // 같은 위치의 인접한 숫자 검사
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m; j++) {
            if (c[i][j] == 0) continue;
            if (c[i][j] == c[i + 1][j]) {
                adj[i][j] = true;
                adj[i + 1][j] = true;
            }
        }
    }

    // 인접한 숫자들 제거
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (adj[i][j]) {
                c[i][j] = 0;
                chk++;
            }
            if (c[i][j] != 0) non_zero++;
            ans += c[i][j];
        }
    }

    // 평균을 정확하게 하기 위해서 double 자료형 사용
    double tmp = ans;
    // 제거할 숫자가 없는 경우 평균값을 구해서 증가시킴
    if (chk == 0) {
        ans = 0;
        tmp /= non_zero;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (c[i][j] == 0) continue;
                if (c[i][j] > tmp) c[i][j]--;
                else if (c[i][j] < tmp) c[i][j]++;
                ans += c[i][j];
            }
        }
    }
}

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

    cin >> n >> m >> t;
    c = vector<vector<int>>(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> c[i][j];

    for (int i = 0; i < t; i++) {
        int x, d, k;
        cin >> x >> d >> k;
        spin(x, x, d, k);
        remove();
    }
    cout << ans << '\n';
    return 0;
}