[25.03.13] ps study 백준 17822 원판 돌리기 리뷰(c++)

luke  · 

백준 17822 원판 돌리기

17822 문제 바로가기
문제 정리
  1. 2차원 배열을 n/x 번 회전시킴
  2. 상하좌우 인접을 체크 (원형이기 때문에 y가 -1인 경우 -> n-1, y가 n인 경우 -> 0)
  3. 인접한 게 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.
풀이 전략

배열의 회전 모듈러 연산을 활용한 회전해서 삽입될 인덱스 찾기 ex: 가로 크기가 4일 때 (3+2)%4=1, (1+2)%4=3

vector<int> temp(m);
for (int i = 0; i < m; i++)
{
    int nx = (i + (d * k) + m) % m;
    temp[nx] = arr[y - 1][i];
}
for (int i = 0; i < m; i++)
    arr[y - 1][i] = temp[i];

인접 판별 다음 검색에 문제가 될 수 있으니, 인접한 부분들은 표시만 해두기 2차원 배열의 열은 원형이기 때문에 -1 -> m-1, m-> 0

for (int l = 0; l < 4; l++)
{
    int ny = i + dy[l];
    int nx = j + dx[l];
    if (ny < 0 || ny >= n)
        continue;
    if (nx < 0)
        nx = m - 1;
    else if (nx >= m)
        nx = 0;
    if (arr[ny][nx] == val)
    {
        mark[i][j] = true;
        mark[ny][nx] = true;
        isSame = true;
    }
}
제출한 코드
#include <bits/stdc++.h>
#define fastio cin.tie(NULL)->sync_with_stdio(0)
using namespace std;
int n, m, t, x, d, k;
int arr[51][51];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};

void rotateArr(int x, int d, int k)
{
    for (int y = x; y <= n; y += x)
    {
        vector<int> temp(m);
        for (int i = 0; i < m; i++)
        {
            int nx = (i + (d * k) + m) % m;
            temp[nx] = arr[y - 1][i];
        }
        for (int i = 0; i < m; i++)
            arr[y - 1][i] = temp[i];
    }
}

int main()
{
    fastio;
    cin >> n >> m >> t;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> arr[i][j];

    while (t--)
    {
        cin >> x >> d >> k;
        // 문제 의도에 따라 d가 0이면 시계, 1이면 반시계라면 아래와 같이 처리
        d = (d ? -1 : 1);
        rotateArr(x, d, k);

        // 인접하면서 수가 같은 것을 체크하기 위한 별도의 마크 배열
        bool isSame = false;
        bool mark[51][51] = {false,};

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (arr[i][j] == 0)
                    continue;
                int val = arr[i][j];
                for (int l = 0; l < 4; l++)
                {
                    int ny = i + dy[l];
                    int nx = j + dx[l];
                    if (ny < 0 || ny >= n)
                        continue;
                    if (nx < 0)
                        nx = m - 1;
                    else if (nx >= m)
                        nx = 0;
                    if (arr[ny][nx] == val)
                    {
                        mark[i][j] = true;
                        mark[ny][nx] = true;
                        isSame = true;
                    }
                }
            }
        }

        // 표시된 위치를 한 번에 0으로 변경
        if (isSame)
        {
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    if (mark[i][j])
                        arr[i][j] = 0;
        }
        else
        {
            // 인접한 같은 수가 없으면 평균을 구한 뒤 조정
            double sum = 0;
            int cnt = 0;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    if (arr[i][j])
                    {
                        sum += arr[i][j];
                        cnt++;
                    }
            if (cnt != 0)
            {
                double avg = sum / cnt;
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < m; j++)
                        if (arr[i][j])
                        {
                            if (arr[i][j] > avg)
                                arr[i][j]--;
                            else if (arr[i][j] < avg)
                                arr[i][j]++;
                        }
            }
        }
    }

    int res = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            res += arr[i][j];

    cout << res << "\n";
    return 0;
}