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

문제

반지름 N짜리
반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있다.

T개의 줄에 나온 정보에 따라 회전을 시키고 인접한 수들을 삭제한다.
삭제할 게 없으면 원판 전체 수의 합의 평균보다 작으면 1증가, 크면 1감소 시킨다.
모든 회전이 끝나고 최종 원판에 적힌 수의 합을 출력하는 문제다.

풀이

원판 입력은 배열 벡터 vector<int> v[51]로 받아서 다음과 같이 저장했다.

원판 입력이 끝나면 아래와 같은 루틴이 t번 반복된다.

1. 회전 정보입력(x,d,k)
2. x의 배수인 원판 d방향으로 k칸 회전
3. 인접한 같은 수 체크 & 삭제
4. 인접한 같은 수 없었으면 평균과 비교해서 값 바꾸기

원판 회전은 벡터 rotate를 이용했다.

rotate(v[i].begin(), v[i].begin() + (m - 1), v[i].end()); //시계방향
rotate(v[i].begin(), v[i].begin() + 1, v[i].end()); //반시계방향

인접 수 체크는 dfs를 이용했다. y = 원판 번호, x = 원판 내 번호 idx
주의해야할 점은 원형이기 때문에 x가 0일때 v[y][m-1]과 같은 값인지 체크해야한다.
인접한 것끼리 지워진 수가 없다면 원판 내 모든 수를 더하고 평균을 구해서 원판 내 남은 수들의 값을 비교 후 바꿔준다. 평균은 소수점이 나올 수 있기 때문에 float를 사용했다.
(이 과정에서 평균값을 저장하는 변수 tot을 초기화안해서 계속 틀렸다고 떴다..; 모든 반례가 돌아갔는데 사소한 것때문에 시간을 많이 썼다ㅠ)

t번의 입력과 계산이 끝났으면 원판 내 모든 수의 합을 출력한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, t, x, d, k, a, res, visited[51][51], dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
vector<int> v[51];
float cnt, tot;

void go(int y, int x, int c)
{
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (x == 0 && nx == -1)
            nx = m - 1;
        if (x == m - 1 && nx == m)
            nx = 0;
        if (ny < 1 || ny > n || nx < 0 || nx >= m || visited[ny][nx])
            continue;
        if (v[ny][nx] == c)
        {
            v[y][x] = 0;
            v[ny][nx] = 0;
            visited[ny][nx] = 1;
            cnt++;
            go(ny, nx, c);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> t;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a;
            v[i].push_back(a);
        }
    }
    for (int p = 0; p < t; p++)
    {
        cin >> x >> d >> k;
        for (int i = 1; i <= n; i++)
        {
            if (i % x == 0)
            {
                if (d == 0)
                {
                    for (int j = 0; j < k; j++)
                        rotate(v[i].begin(), v[i].begin() + (m - 1), v[i].end());
                }
                else
                    for (int j = 0; j < k; j++)
                        rotate(v[i].begin(), v[i].begin() + 1, v[i].end());
            }
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (v[i][j] && !visited[i][j])
                {
                    visited[i][j] = 1;
                    go(i, j, v[i][j]);
                }
            }
        }

        if (cnt == 0)
        {
            for (int i = 1; i <= n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (v[i][j])
                    {
                        tot += v[i][j];
                        cnt++;
                    }
                }
            }
            tot /= cnt;
            for (int i = 1; i <= n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (v[i][j])
                    {
                        if (v[i][j] > tot)
                            v[i][j] -= 1;
                        else if (v[i][j] < tot)
                            v[i][j] += 1;
                    }
                }
            }
        }
        cnt = 0, tot = 0;
        fill(&visited[0][0], &visited[0][0] + 51 * 51, 0);
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < m; j++)
            res += v[i][j];
    }
    cout << res << "\n";
}