문제

in Blog_old on Boj, 삼성sw역량테스트기출, C++

링크

원주를 따라 시계방향으로 $M$개의 숫자가 써있는 원판 $N$개가 동심원의 형태를 띄며 놓여있다. 입력에 따라 원판을 회전 시켜야하는데, 회전 시킨 이후에 인접한 수와 서로 같은 것이 있다면 모두 지운다. 없다면 모든 원판에 적힌 숫자의 평균을 구하고, 그보다 작은것에는 +1, 큰 것에는 -1해준다. 최종적으로 원판에 남아있는 모든 숫자의 합을 구하는 문제이다.

접근

격자판에 DFS/BFS돌리던 지난 문제들에서 약간의 변형이 추가되었다. 원판 끼리는 첫 원판과 마지막 원판이 인접하지 않지만, 원판 안에서는 첫 숫자와 마지막 숫자가 인접한다.

원판이지만 그냥 2차원 배열 내지는 deque<int>의 배열로 정의하여 두고, std::rotate함수를 잘 활용하여 원판 회전을 구현해주자. 회전한 다음에는 2차원 배열에서 하듯이 DFS를 해주면 되는데, 주의할 점은 원판 안의 숫자는 첫 숫자와 마지막 숫자가 인접해야 한다는 것이다. 인덱스가 -1 또는 M이면 처리하는 방법도 있겠지만, 아래 코드에서와 같이 나머지 연산을 활용하여 int ny=(y+M+dy[d])%M해주면 if문 없이 이를 처리할 수 있다.

원판에서 숫자를 지운다는 것은 0으로 바꾸는 것으로 처리하면 깔끔하다. 대신, 평균을 구해야 하는 경우가 있으므로 원판에 남아있는 숫자 갯수는 저장해 두어야 한다. 아래 코드에는 각 원판의 숫자 개수를 저장하게 되어있는데, 사실 총 갯수만 저장해도 지장은 없을 것 같다.

숫자를 한번도 지우지 못했다면, 평균과 비교하여 +1/-1해주어야 한다. 따라서 성공 여부를 boolean으로 받아서, 실패했다면 이 부분을 처리해주면 된다. 이건 그냥 평균과 비교해서 1 증가/감소하는거라 간단하다.

주의할 점

회전을 구현할 때, 시계방향 회전과 반시계방향 회전이 있으니 틀리지 않게 주의하자.

또, 평균은 원판별로 구하는 것이 아니라 모든 원판에 대해서 구하는 것이다.

Code

링크

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

using namespace std;

int N, M, T;
deque<int> A[50];
int num[50] = {0};
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

bool dfs(int x, int y, int target) {
    bool ret = false;
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d];
        int ny = (y + M + dy[d]) % M;  // to make circular structure.
        if (0 <= nx && nx < N && A[nx][ny] == target) {
            A[nx][ny] = 0;  // erase
            num[nx]--;
            ret = true;
            dfs(nx, ny, target);
        }
    }
    return ret;
}

bool dfs() {
    bool ret = false;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (A[i][j] != 0 && dfs(i, j, A[i][j])) {
                ret = true;
            }
        }
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // get input
    cin >> N >> M >> T;
    int tmp;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> tmp;
            A[i].push_back(tmp);
        }
    }
    for (int i = 0; i < N; i++) {
        num[i] = M;
    }

    int x, d, k;
    while (T--) {
        cin >> x >> d >> k;
        for (int curr = x - 1; curr < N; curr += x) {
            if (d == 0) {
                rotate(A[curr].rbegin(), A[curr].rbegin() + k, A[curr].rend());  // CW
            } else {
                rotate(A[curr].begin(), A[curr].begin() + k, A[curr].end());  // CCW
            }
            // cout << "after rotation:" << '\n';
            // for (int i = 0; i < N; i++) {
            //     for (int j = 0; j < M; j++) {
            //         cout << A[i][j] << ' ';
            //     }
            //     cout << '\n';
            // }
        }
        if (!dfs()) {
            int sum = 0;
            int total = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    sum += A[i][j];
                }
                total += num[i];
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (A[i][j] != 0) {
                        if (A[i][j] * total > sum) {
                            A[i][j]--;
                        } else if (A[i][j] * total < sum) {
                            A[i][j]++;
                        }
                    }
                }
            }
        }
        // cout << "now:" << T << '\n';
        // for (int i = 0; i < N; i++) {
        //     for (int j = 0; j < M; j++) {
        //         cout << A[i][j] << ' ';
        //     }
        //     cout << '\n';
        // }
    }

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

    cout << ans;
    return 0;
}

여담

  • 사실 std::rotate()함수의 존재는 몰랐는데, 이번 기회에 알게 되었다. 여기가 도움이 되었다.
  • 위 코드에서 주석 처리한 부분은, 디버깅할 때 rotation이 어떻게 일어나는지 확인하기 좋은 곳이다.