[삼성SW테스트] 백준 17822번 - 원판 돌리기 (정답률 31%)

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

17822번: 원판 돌리기

2019년 하반기 삼성 SW테스트 문제다.

이 문제는 시뮬레이션을 풀듯이 풀 수도 있으며, dfs 탐색을 통해 풀 수도 있다.

어느쪽이던 편한대로 풀어도 무방할 문제인거같다.

 

   유의할 점은

1. 인접수가 없을 경우 0의 개수를 고려하지 않고 평균을 계산해 0이 아닌 숫자에만 적용을 해줘야 하는 것과

2. row/col의 범위를 잘 고려해 인접수를 구하는 것 정도가 되겠다.

 

아래는 소스코드 (C++, 4ms)

#include <iostream>
#include <vector>
#include <algorithm>
#define maxlen 51
using namespace std;
int N, M, T, x, d, k;
int circles[maxlen][maxlen];
bool no_adj_num = true;
vector<pair<int, int> > erase, real_erase;
vector<pair<int, pair<int, int> > > orders;
typedef struct dir{
    int dr, dc;
}dir;
dir direction[4] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
void rotate(int row, int kan){
    // 시계방향 회전
    vector<int> temp(M + 1, 0);
    for (int col = 1; col <= M; col++){
        if (col + kan > M){
            temp[col + kan - M] = circles[row][col];
        }
        else
            temp[col + kan] = circles[row][col];
    }
    for (int col = 1; col <= M; col++)
        circles[row][col] = temp[col];
    //temp.clear();
}
void dfs(int curnum, int r, int c){
    erase.push_back(make_pair(r, c));
    for (int i = 0; i < 4; i++)
    {
        int nr = r + direction[i].dr;
        int nc = c + direction[i].dc;
        if (nr >= 1 && nr <= N && nc >= 1 && nc <= M){
            if (curnum == circles[nr][nc])
                erase.push_back(make_pair(nr, nc));
        }
        else if (nr == 0){
            continue;
        }
        else if (nr > N) continue;
        else if (nc == 0){
            if (circles[nr][M] == curnum)
                erase.push_back(make_pair(nr, M));
        }
        else if (nc == M + 1){
            if (circles[nr][0] == curnum)
                erase.push_back(make_pair(nr, 0));
        }
    }
    if (erase.size() > 1) {
        no_adj_num = false;
        for (int i = 0; i < erase.size(); i++){
                real_erase.push_back(erase[i]);
        }
    }
    erase.clear();
}
 
void Simulation(int th_order){
    int curx = orders[th_order].first;
    int dir = orders[th_order].second.first;
    int kan = orders[th_order].second.second;
 
    // 1. 회전.
    for (int row = 1; row <= N; row++){
        if (row % curx == 0){
            if (dir == 1){
                rotate(row, M - kan);
            }
            else
                rotate(row, kan);
        }
    }
 
    // 2-1. 인접수 확인.
    for (int r = 1; r <= N; r++){
        for (int c = 1; c <= M; c++){
            if (circles[r][c] != 0){
                dfs(circles[r][c], r, c); // 인접수 있는 경우 지우고, no_adj_num false로. 없는경우 넘어감.
            }
        }
    }
    // 2-2. 인접수 없는 경우
    if (no_adj_num){
        int sum = 0;
        int cnt = 0;
        for (int r = 1; r <= N; r++){
            for (int c = 1; c <= M; c++){
                if (circles[r][c] != 0) {
                    cnt++; // 이게 문제.
                    sum += circles[r][c];
                }
            }
        }
        double average = (double)sum / (double)cnt;
        for (int r = 1; r <= N; r++){
            for (int c = 1; c <= M; c++){
                if (average > (double)circles[r][c] && circles[r][c] != 0){
                    circles[r][c]++;
                }
                else if (average < (double)circles[r][c] && circles[r][c] != 0)
                    circles[r][c]--;
            }
        }
    }
    for (int i = 0; i < real_erase.size(); i++){
        int curr = real_erase[i].first;
        int curc = real_erase[i].second;
        circles[curr][curc] = 0;
    }
    real_erase.clear();
    /*
    cout << '\n';
    for (int i = 1; i <= N; i++){
    for (int c = 1; c <= M; c++){
    cout << circles[i][c] << " ";
    }
    cout << '\n';
    }
    */
    no_adj_num = true;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N >> M >> T;
    for (int row = 1; row <= N; row++){
        for (int col = 1; col <= M; col++){
            cin >> circles[row][col];
        }
    }
    for (int i = 0; i < T; i++){
        cin >> x >> d >> k;
        orders.push_back(make_pair(x, make_pair(d, k)));
    }
    for (int i = 0; i < T; i++)
        Simulation(i);
    int sum = 0;
    for (int r = 1; r <= N; r++)
        for (int c = 1; c <= M; c++)
            sum += circles[r][c];
    cout << sum << '\n';
    return 0;
}