백준 17822번 - 원판 돌리기

www.acmicpc.net/problem/17822

17822번: 원판 돌리기

삼성 SW 역량테스트 문제집의 문제였다.

 

문제를 이해하는 데에는 어렵지 않았지만 구현이 문제였다.

 

일단 "원판"이라는 단어를 보자마자 deque로 구현해야겠다고 생각했다.

 

구현의 큰 틀은 아래와 같다.

 

1. 원판을 생성한다 (deque 사용)

2. 원판을 T번 돌린다

 - 1) 인접한 수들을 검사한다. 

 - 2) 인접한 수가 있다면 제거, 없다면 평균 구해서 규칙에 맞게 가감

 

이제 구체적인 구현을 살펴보자.

 

인접한 수들을 검사할 때 신경 써야 하는 부분은 좌, 우로 인접해있다면 원형적으로 생각해야 한다 였다.

 

문제의 조건중

 

• (i, 1)은 (i, 2), (i, M)과 인접하다.
• (i, M)은 (i, M-1), (i, 1)과 인접하다.
• (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)

이 조건 때문에 좌 우는 원형적으로 생각해줘야 한다. 

(원형적으로 생각한다는 말은 만약 (i, j)에서 j가 m, 즉 범위를 벗어났다면 0으로 생각해줘야 한다는 의미이다.)

 

if (ny < 0) { // 좌측 범위를 벗어났다면
	ny = m - 1;
}
else if (ny >= m) { // 우측 범위를 벗어났다면
	ny = 0;
}

 

상, 하 관계는 따질 필요가 없다. (문제의 조건에 명시)

 

이렇게 인접한 수들을 체크하고 나는 check배열에 담아 놓고 한 번에 제거해주었다.

 

또 전체 합을 담은 변수를 미리 생성해 놓고 제거하거나 더해줄 때 사용함으로써 평균을 구해야 할 때 매번 더하는 쓸데없는 짓은 하지 않았다.

 

처음엔 어렵지 않을 것이라 생각하고 구현했는데 하다보니 생각보다 코드가 길어지고 복잡해졌다..

 

최적화한 코드는 아님.. 귀찮아.. 그냥 의식의 흐름대로 짠 코드..

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstring>
using namespace std;
 
int n, m, t, e, x, d, k;
deque<int>circle[55];
deque<bool>erase[55];
bool check[55][55];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int all_num = 0, all_cnt = 0;
 
void fill_erase() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            erase[i].push_back(false);
        }
    }
}
 
int main() {
    cin >> n >> m >> t;
    all_cnt = n * m;
    fill_erase();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> e;
            circle[i].push_back(e);
            all_num += e;
        }
    }
    while (t--) {
        cin >> x >> d >> k;
        for (int i = 0; i < n; i++) {
            if ((i + 1) % x != 0) continue;
            // 회전
            for (int j = 0; j < k; j++) {
                if (d == 0) {
                    circle[i].push_front(circle[i].back());
                    circle[i].pop_back();
                    erase[i].push_front(erase[i].back());
                    erase[i].pop_back();
                }
                else {
                    circle[i].push_back(circle[i].front());
                    circle[i].pop_front();
                    erase[i].push_back(erase[i].front());
                    erase[i].pop_front();
                }
            }
        }
        // 규칙
            // 1. 인접한 수가 있는지 확인
            // 이때 인접하다 -> 좌우로 인접할 때에는 원형으로 생각해야함
            // 상하는 벗어나면 예외처리
        memset(check, false, sizeof(check));
        bool flag = false;
        for (int a = 0; a < n; a++) {
            if (all_cnt == 0) break; // 더이상 남아있는 수가 없다면 종료
            for (int b = 0; b < m; b++) {
                if (erase[a][b] == true) continue; // 이미 지워진 수라면 
                for (int nk = 0; nk < 4; nk++) {
                    int nx = a + dx[nk];
                    int ny = b + dy[nk];
                    if (nk < 2) { // 좌 우로 인접한 수 확인
                        if (ny < 0) { // 좌측 범위를 벗어났다면
                            ny = m - 1;
                        }
                        else if (ny >= m) { // 우측 범위를 벗어났다면
                            ny = 0;
                        }
                        if (erase[nx][ny] == true) continue;
                        if (circle[a][b] == circle[nx][ny]) {
                            check[a][b] = true;
                            check[nx][ny] = true;
                            flag = true;
                        }
                    }
                    else { // 상 하로 인접한 수 확인
                        if (0 <= nx && nx < n) {
                            if (erase[nx][ny] == true) continue;
                            if (circle[a][b] == circle[nx][ny]) {
                                check[a][b] = true;
                                check[nx][ny] = true;
                                flag = true;
                            }
                        }
                    }
                }
            }
        }
        if (flag == false) { // 만약 인접한 수가 없다면
            double mean = (double)all_num / (double)all_cnt;
            for (int a = 0; a < n; a++) {
                for (int b = 0; b < m; b++) {
                    if (erase[a][b] == true) continue;
                    if ((double)circle[a][b] < mean) {
                        circle[a][b] += 1;
                        all_num += 1;
                    }
                    else if ((double)circle[a][b] > mean) {
                        circle[a][b] -= 1;
                        all_num -= 1;
                    }
                }
            }
        }
        else { // 한번에 인접한 것 처리해야함
            for (int a = 0; a < n; a++) {
                for (int b = 0; b < m; b++) {
                    if (check[a][b] == true) {
                        erase[a][b] = true;
                        all_num -= circle[a][b];
                        all_cnt -= 1;
                    }
                }
            }
        }
    }
    cout << all_num << "\n";
}