저그유저의 프로그래밍

www.acmicpc.net/problem/17406

#include <vector>
#include <cstdio>

using namespace std;

typedef struct Oper
{
    int row, col, start;
}Oper;

int minValue = 987654321;
int n, m;

int min(int a, int b)
{
    return a < b ? a : b; //a가 b 보다 작으면 리턴 a, 아니면 리턴 b
}

//memset을 써도 된다.
void CopyArray(int copyArray[50][50], int arr[50][50])
{
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            copyArray[i][j] = arr[i][j];
        }
    }
}

void RotateRight(int arr[50][50], int copyArray[50][50], int r, int c, int s)
{
    if (s == 0)
    {
        return;
    }
    
    int up = r - s;
    int down = r + s;
    int left = c - s;
    intt right = c + s;

    for (int i = left + 1; i <= right; ++i)
    {
        copyArray[up][i] = arr[up][i - 1];
    }

    for (int i = up + 1; i <= down; ++i)
    {
        copyArray[i][right] = arr[i - 1][right];
    }

    for (int i = right - 1; i >= left; --i)
    {
        copyArray[down][i] = arr[down][i + 1];
    }

    for (int i = down - 1; i >= up; --i)
    {
        copyArray[i][left] = arr[i + 1][left];
    }

    //s를 줄여 점점 줄여가며 안쪽도 회전시켜준다.
    RotateRight(arr, copyArray, r, c, s - 1);
}

void RotateArray(int arr[50][50], vector<Oper>& v, vector<bool> &usedCheck, int needUse)
{
    if (needUse == 0) //모든 회전을 다 했다면
    {
        //전체 행 각각 합을 구하고 정답을 갱신한다.
        for (int i = 0; i < n; ++i)
        {
            int sum = 0;
            for (int j = 0; j < m; ++j)
            {
                sum += arr[i][j];
            }
            minValue = min(minValue, sum);
        }
        return;
    }

    int copyArray[50][50];
    int size = usedCheck.size();
    for (int i = 0; i < size; ++i)
    {
        if (usedCheck[i]) //이미 쓴 회전은 넘어간다.
        {
            continue;
        }

        usedCheck[i] = true; //회전 체크
		
        int r = v[i].row;
        int c = v[i].col;
        int s = v[i].start;

        CopyArray(copyArray, arr); //회전을 위해 배열 복사
        RotateRight(arr, copyArray, r, c, s); //오른쪽 회전을 한다.
        RotateArray(copyArray, v, usedCheck, needUse - 1); //다음 회전을 하러 간다.
		
        usedCheck[i] = false; //회전 체크 해제
    }
}

int main()
{
    vector<Oper> v;
    vector<bool> usedCheck;
    int arr[50][50] = { 0 };
    int k, r, c, s;

    scanf("%d %d %d", &n, &m, &k);
    usedCheck.resize(k);

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            scanf("%d", &arr[i][j]);
        }
    }

    for (int i = 0; i < k; ++i)
    {
        scanf("%d %d %d", &r, &c, &s);
        r--; //0부터 시작하는 배열을 쓸거기 때문에 1씩 줄여준다.
        c--; //위와 마찬가지

        v.push_back({ r, c, s });
    }

    RotateArray(arr, v, usedCheck, k); //돌린다.

    printf("%d\n", minValue);
}

문제를 간단히 정리해보면 n x m 배열을 행, 열 (r, c) 축을 기준으로 s 크기만큼의 영역만 돌리고,

각 행별로의 숫자들의 합이 최소가 되는 값을 찾는 문제이다.

이 때 r, c, s 는 k개까지 입력을 받고, 모든 회전을 다 해봐야된다.

만약 회전의 방법이 3가지라면

1 2 3

  3 2

2 1 3

  3 1

3 1 2

  2 3

( 3! = 6 ) 개 만큼의 모든 상황들을 시뮬레이션 해봐야 한다. 최대 ( 6! = 6x5x4x3x2x1 = 720 ) 가지 방법이 될 수 있다.

문제는 배열 돌리기 (해당 좌표에 대해서만) + 욕심쟁이 방법 (=브루트 포스), 두 가지를 통해 해결해야 된다.

가장 중요한 배열 돌리기에 대해서 살펴보면

              (시계 방향으로 회전)

1 2 3        4 1 2

4 5 6  =>  7 5 3

7 8 9        8 9 6

1칸씩 밀리는 방법이다.

배열의 주소를 이용하여 *( *(arr + i) + j) 와 같은 방법으로도 해결해 볼 수 있는 것 같지만, 복잡할거 같아 지금은 넘어가고, 직관적으로 풀어나가는 것이 좋을거라 생각 된다.

먼저 A 배열을 복사할 새로운 B 배열이 필요하고 

      1 2 3         x x x

A = 4 5 6    B = x x x

      7 8 9         x x x

다음과 같은 방법으로 배열을 돌릴 수 있다. 오른쪽, 아래, 왼쪽, 위 순서로 채워나갈 수 있다.

오른쪽으로 먼저 채운다. B는 아래와 같은 상태가 된다.

       x 1 2

B =  x x x

       x x x

for ( int i = left + 1; i <= right; ++i )

   B[ up ][ i ] = A[ up ][ i - 1 ];

즉 up = 0, left = 0, right = 2라면

  B[0][1] = A[0][0] (1)

  B[0][2] = A[0][1] (2)

가 된다. 다음으로 아래쪽으로 채우게 된다면?

       x 1 2

B =  x x 3

       x x 4

for ( int i = up + 1; i <= down; ++i )

   B[ i ][ right ] = A[ i - 1 ][ right];

왼쪽으로 채우면

       x 1 2

B =  x x 3

       6 5 4

(가장 오른쪽 - 1 에서 왼쪽까지 가기때문에 마이너스가 된다. 물론 플러스로 구현해도 상관없다.)

for ( int i = right - 1; i >= left; --i )

   B[ down ][ i ] = A[ down ][ i + 1]; 

마지막으로 위로 채우면

       8 1 2

B =  7 x 3

       6 5 4

for ( int i = down - 1; i >= up; --i )

   B[ i ][ left ] = A[ i + 1][ left ];

이런식으로 채워지게 된다. 먼저 이 회전에 대해서 이해하고, 나머지는 반복적인 재귀로 처리할 것!

분명히 나중에 또 까먹겠지.. ㅠㅠ