17822번 원판 돌리기

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

bfs로 풀었다.

퍼져나가는 방향을 생각해보니

상하좌우로 퍼져나가므로 bfs를 떠올렸다.

그리고, 첫 행과 마지막 행은 같아야 한다.

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 52
 
int N, M, T, x, d, k;
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
bool visit[Max][Max], isDelete;
vector<vector<int> > circle;
vector<pair<int, int> > bv;
 
void Update()
{
    k %= M;
 
    for (int j = 0; j < N; j++)
        if ((j + 1) % x == 0)
        {
            vector<int> temp;
            for (int i = 0; i < M; i++) temp.push_back(circle[i][j]);            
            for (int t = 0; t < k; t++)
                if (d == 0) // 시계
                {
                    temp.insert(temp.begin(), temp.back());
                    temp.pop_back();
                }
                else if (d == 1) // 반시계
                {
                    temp.push_back(temp.front());
                    temp.erase(temp.begin());
                }
            
            for (int i = 0; i < M; i++)
                if (i == 0) circle[i][j] = circle[M][j] = temp[i];
                else circle[i][j] = temp[i];            
        }
}
 
void bfs(queue<pair<int, int> > q, int now)
{
    while (!q.empty())
    {
        int qs = q.size();
 
        while (qs--)
        {
            int r = q.front().first;
            int c = q.front().second;
 
            q.pop();    
            
            for (int i = 0; i < 4; i++)
            {
                int y = r + dy[i];
                int x = c + dx[i];
 
                if (y < 0 || y > M || x < 0 || x >= N || circle[y][x] != now || visit[y][x]) continue;
 
                visit[y][x] = true;
                q.push({ y, x });
                bv.push_back({ y, x });
            }
        }
    }
 
    if (bv.size() >= 2)
        for (auto i : bv)
        {
            isDelete = true;
            if (i.first == 0) circle[M][i.second] = 0;
            circle[i.first][i.second] = 0;
        }
}
 
void Delete()
{
    isDelete = false;
 
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
        {
            if (circle[i][j] == 0) continue;
 
            queue<pair<int, int> > q;
            memset(visit, false, sizeof(visit));
            bv.clear();
            int now = circle[i][j];
 
            q.push({ i, j });
            visit[i][j] = true;
            bv.push_back({ i, j });
 
            if (i == 0)
            {
                q.push({ M, j });
                visit[M][j] = true;
            }
 
            bfs(q, now);
        }
    
 
    if (!isDelete)
    {
        double sum = 0.0, cnt = 0.0;
 
        for (int i = 0; i < M; i++)
            for (int j = 0; j < N; j++)
            {
                if (circle[i][j] == 0) continue;
 
                sum += (double)circle[i][j];
                ++cnt;
            }    
        
        double avg = sum / cnt;
 
        for (int i = 0; i < M; i++)
            for (int j = 0; j < N; j++)
            {
                if (circle[i][j] == 0) continue;
 
                if ((double)circle[i][j] < avg) ++circle[i][j];            
                else if((double)circle[i][j] > avg) --circle[i][j];
 
                // 이 부분 깜빡
                if (i == 0) circle[M][j] = circle[i][j];
            }
    }
}
 
int answer()
{
    int ret = 0;
 
    for (int i = 0; i < M; i++)
        for (int j = 0; j < N; j++)
            ret += circle[i][j];
    
    return ret;
}
 
int main(void)
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    vector<int> v[Max];
    int input;
    scanf("%d %d %d", &N, &M, &T);
 
    for (int i = 1; i <= N; i++)
        for (int j = 0; j < M; j++)
        {
            scanf("%d", &input);
            v[i].push_back(input);
        }
    
    vector<int> f;
 
    for (int j = 0; j < M; j++)
    {
        vector<int> temp;
        for (int i = 1; i <= N; i++) temp.push_back(v[i][j]);
        if (j == 0) f = temp;
        circle.push_back(temp);
    }
 
    circle.push_back(f);
 
    for (int i = 0; i < T; i++)
    {
        scanf("%d %d %d", &x, &d, &k);
        Update();
        Delete();
    }
 
    printf("%d\n", answer());
 
    return 0;
}