[ 백준 17406 ] 배열 돌리기4 (C++)

백준의 배열돌리기(17406) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 본인은 첫 번째로 할 일을 '순열구현' 으로 생각했다. 회전 연산의 갯수인 K번 배열을 지정된 곳에서 돌려주어야 하는데

   그 순서에 따라서 결과값이 달라질 수 있기 때문에 순열을 구현하였다.

   아직 순열을 구현하는 법을 잘 모른다면 아래의 글을 읽고 오도록 하자.

   [ 순열 구현하는 법 알아보기 ]

   위의 글을 읽고 어떤 순서로 K번 돌릴지까지는 정했다고 생각하겠다.

   그렇다면 이제 할일은 ?? 직접 배열을 돌려보고 최소값을 찾는 것만 남았다.

2) 그럼 이제 직접 배열을 돌려보자. 배열의 시작점 , 끝점, 그리고 돌려야 할 사각형이 총 몇개인지 판단부터 하고 돌리는

   과정으로 들어가보자.

   예제입력1을 기준으로 생각해보자.

   예제입력1에는 { 3, 4, 2 }, 와 { 4, 2, 1 }을 돌리라고 되어있다.

   { 3, 4, 2 } 의 경우를 보면, { 1, 2 }가 시작점, { 5, 6 }이 마지막점으로 사각형을 만들게 된다.

   그림으로 나타내면 이 그림과 같다.

   총 3개의 사각형(파랑색 사각형 + 빨강색 사각형 + 노랑색 사각형) 을 돌려주면 된다.

   그렇다면 { 4, 2, 1 } 을 생각해보자.

   { 4, 2, 1 } 의 경우를 보면, { 3, 1 }이 시작점, { 5, 3 } 이 마지막점으로 사각형을 만들게 된다.

  

   위의 그림과 같이 2개의 사각형을 돌려주어야 한다.

   그렇다면, 몇 개의 사각형을 돌려야 하는지부터 구해보자. 바로 한변의 길이 / 2 이다.

   위에 { 3, 4, 2 } 를 보면 { 1, 2 } 와 { 5, 6 } 이므로, 한 변의 길이 = 4 가 되고, / 2를 하게 되면 2가 된다.

   { 4, 2, 1 }의 경우를 보면, { 3, 1 } 과 { 5, 3 } 이므로 한 변의 길이 = 2 가 되고, /2를 하게 되면 1이 된다.

   근데 숫자들이 조금 이상하다. 분명 { 3, 4, 2 }의 경우 3개의 사각형을, {4, 2, 1} 의 경우 2개의 사각형을 돌려야 한다고

   했는데 사각형의 갯수가 1씩 적다. 왜 ? 어차피 제일 안쪽 사각형은 1x1짜리라서 돌리는게 의미가 없다.

   그럼 이런 경우가 있을수도 있지 않을까 ??

  

   이런 사각형이 나오면 계산을 따로 해줘야 하나 ??

   위의 사각형과 { 3, 4, 2 }, {4, 2, 1} 에 의해서 만들어진 사각형이랑 비교를 해보자. 가장 큰 차이점은 눈에 딱 보이겠지만

   정사각형이냐 직사각형이냐 이다. 그럼 생각을 해보자.

   이런 사각형이 절대 나올리가 없다. 왜냐하면, 사각형이 (r - s, c - s), (r + s, c + s) 를 양 끝점으로

   갖기 때문에 하나의 숫자를 기준으로 동일한 숫자만큼을 빼고 더한 것을 양 끝점으로 갖기 때문에 정사각형이 나올 수 밖에

   없다. 이해가 안되면 수학적 수식으로 계산을 해보면 쉽게 알 수 있다.

   가장 왼쪽 위 칸이(a, b) 이고, 가장 오른쪽 아래칸이 (c, d)일 때, 이 사각형이 정사각형 이기 위해서는

   (c - a) = (d - b) 가 성립을 해야 가로 세로 길이가 같다는 것을 의미하고 정사각형이 된다는 의미이다.

   그렇다면 위의 식을 (r - s, c - s) , (r + s, c + s) 에 그대로 대입해보자.

   ( r + s - ( r - s ) ) = ( c + s - ( c - s ) ) 가 성립하는지를 확인해보면 된다.

   위의 식은 2s = 2s 로 성립을 한다. 즉, 무조건 정사각형이 나오게 된다. 따라서, 위에서 말한 경우를 따로 계산하거나

   할 필요는 없다.

  

3) 2)의 시작말도 배열을 돌려보자 였는데 이제 진짜로 배열을 돌려보자.

   본인은 while문과 방향을 설정하는 변수를 가지고 4변을 한번에 돌리는 식으로 구현해 보았다.

   가장 왼쪽 위의 점을 기준으로 남 -> 동 -> 북 -> 서 방향으로 돌면서 값을 하나씩 움직여 주었다.

   사실 이 부분은 말로 설명하기 보다는 코드를 보면서 이해하는 것이 더 직관적이고 이해하기 쉬울 것 같다.

   코드에 적힌 주석을 보면서 이해해보자..

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 50 + 1
#define K_MAX 6
using namespace std;
 
struct Turn_Info
{
    int R, C, S;
};
 
int N, M, K, R, C, S, Answer;
int MAP[MAX][MAX];
int C_MAP[MAX][MAX];
bool Select[K_MAX];
vector<Turn_Info> V;
vector<int> Turn_Order;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    Answer = 987654321;
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1 ; j <= M; j++)
        {
            cin >> MAP[i][j];
        }
    }
    for (int i = 0; i < K; i++)
    {
        int R, C, S; cin >> R >> C >> S;
        V.push_back({ R,C,S });
    }
}
 
void Copy_MAP()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            C_MAP[i][j] = MAP[i][j];
        }
    }
}
 
int change_Direction(int cur)
{
    if (cur == 0) return 3;
    else if (cur == 1) return 2;
    else if (cur == 2) return 0;
    else if (cur == 3) return 1;
}
 
void Simulation(Turn_Info T)
{
    /*=======================================================================*/
    /*실제로 배열을 돌려보는 함수.
      1. while문을 통해서 각 라인별이 아닌, 한 번에 처리하는 식으로 구현.
      2. 돌려야 할 사각형의 범위 밖으로 나가는 경우 방향을 바꿔주는 식으로 구현. */
    /*=======================================================================*/
 
    int Sx = T.R - T.S;
    int Sy = T.C - T.S;
    int Ex = T.R + T.S;
    int Ey = T.C + T.S;
    int Turn_Count = (Ex - Sx) / 2;    // 몇 개의 사각형을 돌려줘야 하는지 
 
    for (int i = 0; i < Turn_Count; i++)    // 돌려야 할 사각형의 갯수만큼 반복
    {
        int x = Sx;                    // x = 시작 X좌표
        int y = Sy;                    // y = 시작 y좌표
        int Temp = C_MAP[x][y];        // 가장 첫 시작점을 Temp에 임시적으로 저장
        int d = 2;                    // 0 = 동, 1 = 서, 2 = 남, 3 = 북. 첫 방향은 남쪽 !
        /* 첫 방향을 남쪽으로 잡은 이유 
           - 시계방향으로 배열이 회전되는 것이기 때문에, 이는 어떻게 보면
             자기 자신을 기준으로 반 시계 방향에 있는 값이 자기 자신의 자리에 위치하게 된다.
             즉, 시작점을 기준으로 왼쪽 세로변, 하단 가로변, 우측 세로변, 상단 가로변 순서로 
             움직이면서 값을 설정해 주었다. */
 
        while (1)
        {
            int nx = x + dx[d];    
            int ny = y + dy[d];
            // (nx, ny) = 위에서 말했듯이, 현재 자기자신을 기준으로 한 칸 왼쪽(반시계방향) 에 있는 좌표
 
            if (nx == Sx && ny == Sy)    // 다시 처음 위치로 돌아오게 된다면
            {
                C_MAP[x][y] = Temp;        // 위에서 저장해둔 임시 저장 값으로 값을 설정 후 종료.
                break;
            }
 
            if (Sx <= nx && nx <= Ex - i && Sy <= ny &&  ny <= Ey - i)    // 현재 사각형의 범위 내에 있는 좌표라면
            {
                C_MAP[x][y] = C_MAP[nx][ny];        // 자기자신의 자리에 반 시계방향에 있는 좌표를 넣어준다.
                x = nx;                                // x값 재설정
                y = ny;                                // y값 재설정
            }
            else
            {
                /* 그렇게, 방향을 따라가다 보면 정해진 사각형의 범위를 벗어나는 경우가 존재함. 
                   그럴 때는 방향을 바꿔준다.
                   남쪽 -> 동쪽 -> 북쪽 -> 서쪽 순으로 ! */
                d = change_Direction(d);
            }
        }
        Sx++;    
        Sy++;
        /* 그 다음 사각형으로 가기 위한 Sx, Sy값 설정.
           만약, 돌려야 할 사각형의 갯수가 2개이고, 가장 바깥쪽 사각형의 시작점이 (1, 1)이엿다면
           그 다음으로 돌려야 할 사각형의 시작점은 (2, 2)가 될 것이다. 
           즉, Sx++ ,Sy++ */
    }    
}
 
int Calculate()
{
    /*=======================================================================*/
    /*돌려본 배열에서 모든 행에서 최소값을 갖는 행의 값을 return 해주는 함수. */
    /*=======================================================================*/
    int R_Value = 999999999;
    for (int i = 1; i <= N; i++)
    {
        int Sum = 0;
        
        for (int j = 1; j <= M; j++)
        {
            Sum = Sum + C_MAP[i][j];
        }
        R_Value = Min(R_Value, Sum);
    }
    return R_Value;
}
 
void DFS(int Cnt)
{
    if (Cnt == K)
    {
        /*===========================================================================*/
        /* 순서를 모두 정했을 경우
           1. 맵을 복사해준다. (원본의 맵 유지를 위해서)
           2. 정한 순서대로 ,실제로 맵을 돌려본다. (함수 : Simulation())
           3. 돌려준 맵에서 각 행의 최소값을 찾아서 Answer값을 갱신.*/
        /*===========================================================================*/
        Copy_MAP();
        for (int i = 0; i < Turn_Order.size(); i++)
        {
            int Order = Turn_Order[i];
            Simulation(V[Order]);
        }
        Answer = Min(Answer, Calculate());
        return;
    }
 
    /* 배열을 돌리는 순서를 정하기 위한 (순열 생성을 위한) 반복문. */
    for (int i = 0; i < V.size(); i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        Turn_Order.push_back(i);
        DFS(Cnt + 1);
        Turn_Order.pop_back();
        Select[i] = false;
    }
}
 
void Solution()
{
    /*================================================================================================*/
    /* 순열 구현을 통해서 어떤 순서로 돌릴지 순서를 정해준다.*/
    /*================================================================================================*/
 
    DFS(0);
    cout << Answer << endl;
 
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}