[백준] 17882번

17882 원판돌리기

문제

---

반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 

원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 

각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다.

- (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)

아래 그림은 N = 3, M = 4인 경우이다.

원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.

1. 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
2. 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.

그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.

없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.

입력

---

첫째 줄에 N, M, T이 주어진다.

둘째 줄부터 N개의 줄에 원판에 적힌 수가 주어진다. i번째 줄의 j번째 수는 (i, j)에 적힌 수를 의미한다.다음 T개의 줄에 xi, di, ki가 주어진다.

출력

---

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 출력한다.

제한

---

- 2 ≤ N, M ≤ 50

- 1 ≤ T ≤ 50

- 1 ≤ 원판에 적힌 수 ≤ 1,000

- 2 ≤ xi ≤ N

- 0 ≤ di ≤ 1

- 1 ≤ ki < M

---

풀이)

문제는 어려운 문제가 아니였지만, 구현에 있어서 애를 먹은 문제이다.

딱히 요구하는 알고리즘이 있는 것이 아니라 진짜 문제 자체를 하나씩 서술하면 되는 문제였다.

주의할점

1. x의 배수의 원판이라는 말은 x*1, x*2, x*3 .... 원판을 뜻한다. 처음에 x에다가 계속 2씩 곱하는 바람에 틀렸다.

2. 인접한 수를 바로 지우면 안된다. 바로 지우게 될 경우 그 수와 인접한 다른 수를 확인할 수 없기 때문이다.

3. 평균구하기. 평균을 처음에 int형으로 두었다가 답이 안나와서 헤맸다. 

   평균을 float이나 double형으로 두고, 평균보다 큰 수와 평균보다 작은 수로 나눠야한다.

코드)

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
//n은 원판수, m은 원판에 각자적혀있는 숫자 수
int n, m, t;
int arr[51][51]; //[i][j] = i번째 원판에 j번째 수
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int cnt;//원판에 적힌 수의 개수
int hop; //원판의 적힌 수들의 값 합
bool visited[51][51];
 
int main() {
    scanf("%d %d %d", &n, &m, &t);
 
    cnt = n * m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &arr[i][j]);
            hop += arr[i][j];
        }
    }
 
    while (t--)
    {
        int x, d, k;
        scanf("%d %d %d", &x, &d, &k);
 
        //1. x배수인 원판들을 k번 회전
        k %= m; //회전시간을 줄이기위해
        //여기서 처음에 틀림
        //배수라는 말을 잘못이해해서 i*2로 계산함
        for (int i = x; i <= n; i += x) {
            int ntmp = 0;
            int temp = 0;
            //k번회전
            for (int t = 0; t < k; t++) {
                //시계방향
                if (d == 0) {
                    ntmp = arr[i][1];
                    for (int j = 2; j <= m; j++) {
                        temp = arr[i][j];
                        arr[i][j] = ntmp;
                        ntmp = temp;
                    }
                    arr[i][1] = ntmp;
                }
                else {//반시계방향
                    ntmp = arr[i][m];
                    for (int j = m - 1; j >= 1; j--) {
                        temp = arr[i][j];
                        arr[i][j] = ntmp;
                        ntmp = temp;
                    }
                    arr[i][m] = ntmp;
                }
            }
            
        }
        //2.인접하면서 수가 같은 것 찾기
        bool total = false;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (arr[i][j] == -1) continue;
                bool check = false;
                for (int t = 0; t < 4; t++) {
                    int ny = i + dy[t];
                    int nx = j + dx[t];
                    if (nx == 0) nx = m;
                    if (nx > m) nx = 1;
                    if (ny >= 1 && ny <= n && nx >= 1 && nx <= m) {
                        if (arr[ny][nx] == -1) continue;
                        if (arr[i][j] == arr[ny][nx]) {
                            check = true;
                            total = true;
                            //여기서 바로 arr[ny][nx] = -1으로 바꾸면 이 [ny][nx]값과 인접한 다른 값들을 계산못함
                            //한번에 -1로 변경해줘야함
                            visited[ny][nx] = true;
                        }
                    }
                }
                if (check) {
                    visited[i][j] = true;
                }
            }
        }
 
        //인접한 수가 없었다면
        if (total == false) {
            float temp = (float)hop / cnt; //처음에 평균을 int형으로 둬서 계산이 잘 안됨
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (arr[i][j] == -1) continue; //이전에 지운 수라면 pass
                    if (arr[i][j] > temp) { //평균보다 큰수라면
                        arr[i][j] -= 1;
                        hop -= 1;
                    }
                    else if(arr[i][j] < temp){//평균보다 작은수라면
                        arr[i][j] += 1;
                        hop += 1;
                    }
                }
            }
        }
        //인접한 수가 있었다면
        else {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (visited[i][j] == true) {
                        hop -= arr[i][j];
                        arr[i][j] = -1; // 값 지우기
                        cnt -= 1;
                    }
                }
            }
            //다음 회전을 위해 visited 초기화
            for (int i = 1; i <= n; i++) {
                fill(visited[i], visited[i] + m + 1, false);
            }
        }
    
    }
    
    //합 출력
    printf("%d", hop);
    
    return 0;
}

결과)