[C++] 백준 17822번: 원판 돌리기

문제

난이도 : 골드 2
백준 17822번 : 원판 돌리기

코드

#include <bits/stdc++.h>

using namespace std;

int N, M, T;

vector<int> board[54];  // 원판
set<pair<int, int>> s;  

void Rotate(int idx, int d, int k)
{
    if (d == 0)
    {
        rotate(board[idx].begin(), board[idx].end() - k, board[idx].end());
    }
    else if (d == 1)
    {
        rotate(board[idx].begin(), board[idx].begin() + k, board[idx].end());
    }
}

double Average()
{
    int ret = 0;
    int count = 0;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (board[i][j] == 0)    continue;
            ret += board[i][j];
            count++;
        }
    }

    if (count == 0)  return 0;
    else return (double)ret / count;
}

void adjacent(int i, int j)
{
    if (board[i][j] == board[i][(j + 1) % M])               s.insert({ i, (j + 1) % M });

    if (j != 0 && board[i][j] == board[i][j - 1])           s.insert({ i, j - 1 });
    else if (j == 0 && board[i][j] == board[i][M - 1])      s.insert({ i, M - 1 });

    if (i < N - 1 && board[i][j] == board[i + 1][j])        s.insert({ i + 1, j });
    if (i > 0 && board[i][j] == board[i - 1][j])            s.insert({ i - 1, j });

}

int main()
{
    cin >> N >> M >> T;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            int input; cin >> input;
            board[i].push_back(input);
        }
    }

    while (T--)
    {
        int x, d, k;
        cin >> x >> d >> k;
        
        for (int i = x; i <= N; i += x)
        {
            Rotate(i - 1, d, k);
        }
        
        bool flag = false;

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

                adjacent(i, j);
            }
        }

        if (s.empty())
        {
            double avg = Average();
            if (avg == 0)
                break;

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

                    if (board[i][j] > avg)
                        board[i][j]--;
                    else if(board[i][j] < avg)
                        board[i][j]++;
                }
            }
        }
        else
        {
            for (auto p : s)
            {
                board[p.first][p.second] = 0;
            }
        }

        s.clear();
    }

    int sum = 0;

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

    cout << sum;


    return 0;
}

풀이

구현 문제이다. 생각보다 골드 2치고는 쉬운 편
먼저 원판을 나타내기 위해 나는 이중벡터를 사용했다. vector v[]를 하게 되면 vector 형의 배열이라는 뜻이니까 우리가 구현해야 하는 기능은 크게 2가지 1. i번째 원판 회전 2. 인접한 수 구하기

원판 회전

원판 회전은 rotate 함수만 사용하면 돼서 쉽다. 그리고 x배만큼 증가하는 것도 잘 처리해줄 것
함수 꼴은 rotate(배열의 시작, 중간, 끝)인데 이 중간이란 게 뭐냐면 회전 후 0번째 인덱스로 올 곳?
5 4 3 2 1 배열을 시계 방향으로 1번 돌리면 1 5 4 3 2가 되는데 이 때 중간 매개변수에 (배열의 끝) - 1을 해준다.
사실 내 설명보다 구글에 쳐보면 더 자세하게 설명하신 분들이 많으니 참고

---

이제 원판 회전이 끝났으니 인접 정보를 구하자.

인접

내가 선택한 방법은 board의 모든 인덱스를 방문하며 0이 아닌 수의 위치로 adjacent 함수를 호출했다.
문제에서 설명한 대로 인접한 곳을 보면 board[i][j]의 board[i][j - 1], board[i][j + 1] 그리고 board[i - 1][j], board[i + 1][j]이다.
조건문으로 하나씩 같은 지 확인해보고 인접하면서 같으면 set<pair<int, int>> s에 insert 한다.(이때 배열 밖을 참조하는 일이 벌어지지 않도록 예외 처리 꼭 해주자!)
사실 처음에는 바로 같으면서 인접하면 0으로 처리했는데 내가 선택한 방법은 동시에 일어나는 일이 아니라 차례대로 일어나는 로직이라 바로 0으로 처리하면 뒤에 애들이 처리가 안된다.
그래서 set에 인접하면서 같은 애들을 담아둔다(set이라 중복 X)
그렇게 set에 다 담은 후 set의 size를 보고 비어있으면 평균 구하고 각 인덱스가 평균보다 작으면 +1, 크면 -1 해준다(double처리로)
set이 비어있지않으면 set에 있는 애들을 다 0으로 처리 해준다.
1번 회전이 끝나면 set을 비워주는 것 잊지말기.

---

이제 정답을 구하면 끝이다.

결과