[BOJ] 17822. 원판 돌리기

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

17822번: 원판 돌리기

원판을 회전시키며 인접한 수를 비교하고, 같다면 숫자를 지우는 작업을 반복하는 시뮬레이션 문제이다.

 

 

 

T회만큼 반복하면서 x의 배수인 원판들을 모두 회전시킨 후 인접한 같은 수를 저장해놓았다가 나중에 한 번에 지워준다. (미리 지워서 0으로 만들어버리면 다른 방향으로 인접한 수를 지울 수 없다)

인접한 수 중 같은 숫자인게 없다면 원판에 있는 숫자의 평균을 구해서 평균보다 작으면 1을 증가시켜주고 크면 1을 감소시킨다. 여기서 지워진 숫자는 제외하고 평균을 구해야 한다

 

 

 

//k칸만큼 회전시키기

먼저 k칸만큼 시계방향 회전시킨 방법은 아래와 같이 했다. 예를 들어 k가 4인 경우이다.

편의상 배열은 인덱스가 1부터 시작하도록 구현했다.

 

 

원래 원판에 있던 숫자를 첫 번째부터 tmp배열의 k만큼 떨어진 곳인 5번 자리부터 복사한다. 인덱스가 배열 밖으로 넘어가면 안 되므로 작업을 tmp배열의 마지막 부분인 6번 인덱스까지만 먼저 진행한다.

 

 

 

 

그다음 아래 그림처럼 원판의 나머지 부분을 이어서 tmp배열의 처음 칸부터 k번 인덱스까지 순차적으로 채워주면 된다.

 

시계 반대 방향으로 1번 회전시킨 것은 시계 방향으로 M-1번 회전시킨 것과 같고

마찬가지로 시계 반대 방향으로 2번 회전시킨 것은 시계 방향으로 M-2번 회전시킨 것과 같으므로

같은 함수를 이용해서 회전 횟수를M-k번으로 해주면 된다.

 

 

 

//인접한 숫자 중 같은 수 찾기

 

문제에 나와있는 인접한 수의 조건은 다음과 같다.

• (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)
• (1, j)는 (2, j)와 인접하다.
• (N, j)는 (N-1, j)와 인접하다.
• (i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)

그냥 같은 원판(같은 행) 안에서 바로 양 옆이 인접한 수이고, 바로 위나 아래에 있는 원판 중에서는 같은 열이 인접한 수이다. 그래서 같은 원판 안에서는 마지막 숫자의 옆이 다시 첫 번째 숫자인 것을 처리해주어야 하지만

서로 다른 원판들의 위아래를 비교할 때는 맨 위의 원판과 맨 아래의 원판은 인접한 것이 아니므로 따로 처리해줄 필요는 없다.

 

 

 

//인접한 같은 수 지우기

또, 인접한 같은 수를 미리 지워서 0으로 만들어버리면 다른 방향으로 인접한 수와 비교할 수 없으므로 나중에 한 번에 지워줘야 한다. 그러기 위해서 인접한 같은 수를 가진 좌표들을 저장해놓아야 한다.

중복되는 좌표도 발생할 것 같아서 set을 이용하였다. 인접한 수를 찾으면 set에 원판의 위치(i, j)를 pair로 넣어주고, 나중에 set에서 한 번에 위치를 꺼내서 원판의 해당 위치의 숫자를 지워준다. 

(이때 나는 한쪽 방향으로만 비교하도록 구현했기 때문에 인접한 같은 두 수의 위치를 모두 넣어줬다)

 

 

 

//평균 구해서 더하고 빼주기

위에서 인접한 같은 수가 없어서 지워진 수가 하나도 없다면 문제 조건에 따라

원판에 있는 수들의 평균을 구해서(지워진 수는 제외) 평균보다 높다면 1을 빼주고 평균보다 낮다면 1을 더해준다.

c++에서 int형으로 몫을 구했다면 소수점을 제외한 몫만 저장하므로 나누어 떨어지지 않는 경우를 따로 처리해준다.

 

나누어 떨어지는 경우는 정말 값이 같은 경우이므로 값을 바꿔줄 필요가 없고

나머지가 있다면 실제 값은 몫+나머지 이므로 원판의 값이 평균보다 더 작은 것이므로 1을 더해준다.

 

 

 

//최종 답

T번의 회전이 모두 끝나면 원판의 숫자를 모두 더해준 값이 정답이다.

 

 

 

 

개인적으로 실수한 부분들 메모...

1. 평균을 구하는 과정에서 0으로 나누는 경우가 발생하면 안 된다.
2. 문제 조건에서 평균보다 큰 경우와 작은 경우에 대해만 나와있으므로 같은 경우에는 값이 변하지 않는다.
3. n과 m을 또 반대로 씀... 문제에서 반대로 해놓은 것이 아니었음에도 불구하고...
4. 문제 조건을 제대로 안 읽고, 인접한 수가 없는 경우 평균을 구해서 값을 변경시켜주는 부분을 안봄...
5. 인접한 같은 수 두 개를 set에 넣을 때 하나만 넣어줘서 제대로 안 지워짐

#include <iostream>
#include <set>
using namespace std;
 
int n, m, t;
int board[51][51];
int tmp[51][51];
 
 
void rotate(int i, int count) {
    //i번 원판을 회전
 
    int index = 1;
    for (int j = count+1; j <= m; j++) {
        tmp[i][j] = board[i][index++];
    }
 
    for (int j = 1; j <= count; j++) {
        tmp[i][j] = board[i][index++];
    }
 
 
    //board로 다시 복사
    for (int j = 1; j <= m; j++) {
        board[i][j] = tmp[i][j];
    }
}
 
 
bool removeAdj() {
 
    set<pair<int, int> > s;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
 
            if (board[i][j] == 0) continue;
 
 
            //같은 원판 비교
            if (j == m) {
                //마지막열의 다음은 첫번째열
                if (board[i][m] == board[i][1]) {
                    s.insert(make_pair(i, m));
                    s.insert(make_pair(i, 1));
                }
            }
            else {
                if (board[i][j] == board[i][j + 1]) {
                    s.insert(make_pair(i, j));
                    s.insert(make_pair(i, j + 1));
                }
            }
            
        }
    }
 
 
    //위 아래 원판 비교
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i < n; i++) {
            //지워진 애는 넘어간다.
            if (board[i][j] == 0) continue;
 
            //아래있는 원판과 비교
            if (board[i][j] == board[i+1][j]) {
                s.insert(make_pair(i, j));
                s.insert(make_pair(i + 1, j));
            }
        
        }
    }
 
 
    //인접한 수 중 같은게 없으면 바로 false를 리턴
    if (s.empty()) return false;
 
 
    //set에 들어있는 좌표를 사용하여 모두 지우고 true를 리턴
    set<pair<int, int>> ::iterator iter;
    for (iter = s.begin(); iter != s.end(); iter++) {
        board[iter->first][iter->second] = 0;
    }
 
    return true;
}
 
void calc() {
 
    int sum = 0;
    int total = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (board[i][j] == 0) continue;
 
            total += 1;
            sum += board[i][j];
        }
    }
 
    //숫자가 모두 지워져있다면 바로 리턴
    if (total == 0) return;
    int avg = sum/total;
 
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (board[i][j] == 0) continue;
 
            if (board[i][j] > avg) board[i][j] -= 1;
            else if(board[i][j] < avg) board[i][j] += 1;
            else {
                //나머지가 있다면 board[i][j]의 값이 더 작으므로 +1
                if (sum%total != 0) board[i][j] += 1;
            }
        }
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m >> t;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> board[i][j];
        }
    }
 
    int x, d, k;
    while (t--) {
        cin >> x >> d >> k;
 
 
        for (int i = 1; i <= n; i++) {
            //x의 배수인 원판을 회전
            if (i % x != 0) continue;
 
            
            if (d == 0) {
                //시계방향
                rotate(i, k);
            }
            else {
                //반시계방향
                rotate(i, m - k);
            }
 
        }
        
 
        bool isRemoved = removeAdj();
        if (!isRemoved) {
            //인접한 수 중 같은게 없다면 평균과 비교해 1을 더하거나 빼준다.
            calc();
        }
    }
 
 
    //t회 후에 숫자의 총 합
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ans += board[i][j];
        }
    }
 
 
    cout << ans << '\n';
 
 
    return 0;
}