[ 백준 2549 ] 루빅의 사각형 (C++)

백준의 루빅의 사각형(2549) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

접근하는 방법에 대해서 굉장히 오랫동안 고민했던 문제이다.

가장 단순하게 완전탐색을 하는 경우를 생각해보자. 쉽게 생각하기 위해서 초기에 모든 사각형에 정확한 숫자가 들어있다고

가정하겠다.

지금 현재 위와 같은 상황이라고 가정해 보겠다.

이 상태에서 한 번 움직이게 되면 몇 개가 틀려지는지 알아보자. 여기서 한 번 움직인다라는 것은 "한 행을 오른쪽으로 1 ~ 3칸

중 원하는 칸 수만큼 움직이는 것" 혹은 "한 열을 아래쪽으로 1 ~ 3칸 중 원하는 칸 수 만큼 움직이는 것" 을 의미한다.

그럼 가장 쉽게, 가장 첫 번째 행을 1칸 오른쪽으로 움직인 경우를 생각해보자.

그럼 위와 같은 모양이 될 것이다. 물론, 2칸씩 움직인 경우도, 3칸씩 움직인 경우도 "한 번 움직인 것" 에 해당되게 된다.

즉, 한번의 움직임으로 우리는 최대 3개의 상태를 만들어 낼 수 가 있다.

위의 3개의 그림은 모두 원래의 정확한 맵에서 "한 번 움직였을 때" 나올 수 있는 3가지 상태들을 나타낸 것이다.

즉, 우리는 한번의 움직임으로 3개의 상태를 만들어 낼 수 있다. 그렇다면 이 경우를 완전탐색으로 탐색해보면 몇 가지

경우를 고려해주어야 하는지 생각해보자.

한 번의 움직임으로 3개의 상태를 만들어 낼 수 있고, 우리는 이 한 번의 움직임을 어떤 행을 선택할지 어떤 열을 선택할지

선택할 수 있다. 즉 우리에게는 총 8개의 선택지가 존재한다.(4개의 행 + 4개의 열이 존재하므로)

그럼, 우리는 각 행, 각 열을 한 번씩 움직인다고 가정했을 때, 고려해봐야 할 경우의 수는 8 x 3 = 24 개이다.

왜냐하면, 각 행, 각 열을 한 번씩 움직일 때 마다 총 3개의 상태가 나올 수 있고, 그 3개의 상태가 8개의 선택지에 해당되기

때문에 "한 번 움직일 때 마다 24가지의 경우를 고려" 하게 된다.

그럼 그 이 후에 이 24가지 고려하는 상황을 몇 번을 더 생각해 줘야할까 ? 정말 다행히도 문제에서는 주어진 모든 입력은

"최대 7번" 타일을 움직이게 되면 원래의 정확한 맵과 똑같이 만들 수 있다고 힌트를 주었다.

즉, 24 가지 상황을 최악의 경우 최대 7번 까지 계산을 해야 한다는 것이다.

즉, 24 ^ 7 이 되고, 이는 약 40억이 넘는 연산을 진행하게 된다. 따라서 단순한 완전탐색으로 문제에 접근하게 되면

시간초과를 받게 된다.

따라서 시간초과를 면하기 위해서는 모든 경우를 탐색하는 것이 아닌, 일부 정답이 절대로 될 수 없는 경우들을 탐색하기

전에 미리 걸러주는 과정이 필요하다. 그럼 지금부터 어떤 경우를 걸러낼 수 있을지에 대해서 알아보자.

( 지금부터 사용하는 '정답맵' 이라는 단어는 아래 맵을 의미합니다. )

[ 정답맵 ]

( 또한, '틀린 갯수' 라는 말은, 정답맵과 현재맵을 비교했을 때 제 위치에 있지 않은 원소의 갯수를 의미합니다. )

먼저, 주어진 맵에서 정답맵과 한칸 한칸 비교해서 틀린 갯수를 통해서 앞으로 맵을 몇 번 회전시킬 수 있는지에

대해서 생각을 해보자.

생각해보면 정답맵에서 '한 번'을 움직이게 되면 4개의 숫자가 정답맵과 달라지게 된다.

예를 들어서 정답맵에서 가장 위의 행을 오른쪽으로 한 칸 움직였다고 생각해보자.

이런 형태가 될 것이고, 정답맵과 비교했을 때 첫 번째 행 4개의 숫자가 다르다는 것을 알 수 있다.

즉, 한 번의 움직에 의해서 정답맵과 비교했을 때 숫자가 4개 단위로 달라지게 된다.

위의 맵에서 두 번째 행을 오른쪽으로 한칸 움직여보자.

그럼 위와 같은 형태가 될 것이고, 정답맵과 총 8개의 숫자가 달라지게 된다.

하지만 무조건 4개 단위로 달라지지는 않는다. 첫 번째 행을 오른쪽으로 한 칸 움직인 맵에서 두 번째 행을 움직이는 것이

아니라, 첫 번째 열을 아래쪽으로 한 칸 움직인 상태를 봐보자.

이런 형태가 될 것이다. 정답맵과 비교를 했을 때, 총 7개의 숫자가 다르다. 이런 경우에는 위에서 말한 것 처럼 2번을

움직였음에도, 8개가 아닌 7개가 다르게 된다.

즉, 이 문제는 각각 한 칸 한 칸 단위가 아닌, 한 행 혹은 한 열 단위로 맵이 바뀌기 때문에 절대로 정답맵과 비교했을 때

1개 , 2개 , 혹은 5개 이러한 값들이 나올 수가 없다. 가장 간단하게 생각한다면, 현재 맵과 정답맵을 비교했을 때

틀린 갯수가 4의 배수라면, 틀린 갯수를 4로 나눈 값을 얼추 정답으로 예측할 수 있다.

예를 들어서 현재 맵과 정답 맵의 틀린 갯수를 비교했더니 4개가 나왔다면, 이 '4'라는 숫자를 통해서 "어쩌면, 한 번만 더

움직이면 정답맵이 될 수도 있겠다" 라고 추측할 수 있는 것이다.

하지만 틀린 갯수는 항상 4의 배수로만 존재하지는 않는다고 위에서 말했다. 위의 예시처럼 '7개'와 같이 4의 배수가

아닌 값들이 나올 수가 있다. 왜냐하면, 항상 깔끔하게 행에 대해서만, 열에 대해서만 움직이는 연산이 일어나는 것이 아니라,

행을 움직이고, 열을 움직이는 경우가 존재하기 때문이다. 이런 경우에는 '4의 배수'가 아닌 틀린 갯수가 나오게 될 것이다.

'7개'가 다를 경우에는 아마도 2번 움직이면 정답맵이 될 수도 있습니다 라고 생각을 할 수 있는 것이다.

따라서, '틀린 갯수 % 4' 를 한 값이 0이 아닐 경우, 즉, 4의 배수개로 틀린갯수가 아닐 경우에는 예측 가능한 움직여야 할

횟수를 + 1을 해주는 것이다. 7개로 계산을 해보면 7 / 4 = 1 이라서 일단 한번은 움직여야 하고, 7 % 4 != 0 이므로 + 1 번을

더해서 "아마도 2번을 움직이면 정답맵이 될 수도 있습니다." 라고 계산을 해볼 수 있다.

그런데 위에서 한 이야기들을 보면 굉장히 확신이 없는 말들이 많다. "얼추 정답으로 ~ , 추측할 수 있다 ~ , 아마도 ~"

왜 틀린 갯수가 4개일 때, 확실하게 1번만 돌리면 정답맵이 됩니다 ! 혹은 틀린 갯수가 7개일 때, 확실하게 2번만 돌리면

정답맵이 됩니다 ! 라고 말하지 않고 이런 추측성 말들을 했을까 ?

하나의 예를 들어서 이야기 해보자. 아래의 그림은 틀린 갯수가 7개인 맵이다.

위의 맵은 틀린갯수가 7개인 맵이다. 위의 맵이 나오기 위해서는

1. 정답맵에서 첫 번째 행을 오른쪽으로 한칸 움직인다.

2. 1번에 의해서 생성된 맵에서 첫 번째 열을 아래로 한칸 움직이다.

3. 2번에 의해서 생성된 맵에서 첫 번째 행을 오른쪽으로 2칸 움직인다.

위의 3번의 과정을 통해서 나오는 맵이다. 즉, 우리는 저 맵을 정답맵으로 만들기 위해서 3번을 움직여야 한다는 것을

알고 있다. 하지만 ! 위의 계산대로라면 틀린 갯수는 '7개'이고, 7 / 4 = 1 , 7 % 4 != 0 이므로 1 + 1 = 2

즉, 2번만 돌리면 정답맵이 될 수 있다 라고 계산이 될 것이다. 하지만 2번으로는 절대 위의맵을 정답맵으로 만들지

못할 것이다.

이런 경우가 존재하기 때문에 확실한 표현보다는 추측성 표현을 이용해서 설명을 한 것이다.

그럼 위의 경우는 어떻게 처리해줘야할까 ?? 본인은 사실상 별다른 처리를 해주지 않았다.

왜 ? 아래의 코드를 보면 알겠지만, 위의 맵에서 '2번만 돌리면 정답맵이 될 수 있습니다' 라고 판단을 하고 정말 운좋게

첫 번째 행을 오른쪽으로 2칸 움직였다고 가정해보자. 즉, 3번과정에 의해서 생성된 맵을 다시 2번 과정에 의해서

생성된 맵으로 복구 시켰다고 가정해보자. 그럼에도 똑같이 7개가 틀린 것으로 계산될 것이고, '2번만 더 돌리면 될 수도

있습니다' 라는 판단을 할 수 있기 때문이다. 이 부분은 아래에서 코드와 함께 조금 더 구체적으로 알아보자.

그럼 지금까지 왜 이런 이야기를 했고 무엇을 하기 위해서 이런 이야기를 했는지 정리해보자.

[ 지금까지 위의 내용이 무엇을 위한 과정일까 ? ]

완전탐색으로 모든 경우를 탐색하기에는 너무 많은 경우가 존재하고, 그 많은 경우에서 절대로 정답이 될 수 없는 경우를

걸러주기 위해서 "현재 맵에서 틀린 갯수를 통해서 대략 앞으로 몇 번 더 움직이면 정답맵이 될 수 있는지" 를 파악하기

위해서 틀린갯수와 틀린갯수에 따른 움직이는 횟수를 이야기한 것이다.

[ 그래서 어떤 경우를 걸러줄 수 있을까 ? ]

현재 맵의 상태를 보고 틀린 갯수를 파악할 수 있고, 그 틀린 갯수만으로 "어쩌면 X번만 더 돌리면 정답맵이 될 수도 있겠다"

라는 것을 알아냈으니, "현재 맵을 움직인 횟수 + X번" 한 값이, 기존에 정답으로 채택되어 있는 "움직이는 횟수"보다

더 크다면 굳이 탐색을 할 필요가 없는 것이다.

예를 들어서 기존에 정답으로 채택되어 있는 움직이는 횟수가 '3회' 라고 생각해보자.

즉, 기존에 어떤 방향으로 어떻게 어떻게 하다보니 3번만에 정답맵에 도달한 상태이다.

그런데, 현재 탐색하고 있는 과정에서 보니, "현재 맵을 2번 움직였고, 지금 이 상태에서 틀린 갯수가 8개" 라고 생각해보면

틀린갯수가 8개 이므로 어쩌면 정답맵이 되기 위해서는 2번만 더 돌리면 된다 라는 판단을 할 수 있게된다.

즉, 현재까지 맵을 움직인 횟수 = 2회 + 현재 틀린 갯수를 통해서 추측한 움직여야 할 예상 횟수 = 2회

총 4회가 된다. 이는, 정말로 4회가 걸린다고 하더라도 더 이상 탐색할 필요가 없다. 왜 ? 기존에 이미 3번만에 정답맵에

도달한 경우가 존재하는데 4회 걸리는 경우를 굳이 탐색을 해야할까? 할 필요가 없는 것이다.

이런 경우를 걸러줄 수 있는 것이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 4
using namespace std;
 
int Answer_Cnt = 8;
int Answer_MAP[MAX][MAX];
int MAP[MAX][MAX];
int Process[10][3];
int Answer_Process[10][3];
 
void Input()
{
    int Num = 1;
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            cin >> MAP[i][j];
            Answer_MAP[i][j] = Num++;
        }
    }
}
 
int Compare_MAP()
{
    int Cnt = 0;
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            if (MAP[i][j] != Answer_MAP[i][j]) Cnt++;
        }
    }
    return Cnt;
}
 
void Make_State(int RC, int Idx, int N, bool T)
{
    int Arr[4];
    if (RC == 1) // Idx번 행을, N칸 움직이는 걸로 바꾸겠다.
    {
        if (T == true)
        {
            for (int i = 0; i < 4; i++) Arr[(i + N) % 4] = MAP[Idx][i];
            for (int i = 0; i < 4; i++) MAP[Idx][i] = Arr[i];
        }
        else
        {
            int NN = 4 - N;
            for (int i = 0; i < 4; i++) Arr[(i + NN) % 4] = MAP[Idx][i];
            for (int i = 0; i < 4; i++) MAP[Idx][i] = Arr[i];
        }
    }
    else
    {
        if (T == true)
        {
            for (int i = 0; i < 4; i++) Arr[(i + N) % 4] = MAP[i][Idx];
            for (int i = 0; i < 4; i++) MAP[i][Idx] = Arr[i];
        }
        else
        {
            int NN = 4 - N;
            for (int i = 0; i < 4; i++) Arr[(i + NN) % 4] = MAP[i][Idx];
            for (int i = 0; i < 4; i++) MAP[i][Idx] = Arr[i];
        }
    }
}
 
void DFS(int Cnt)
{
    /* Compare_MAP() = '틀린 갯수' 확인하기. */
    int Default_Count = Compare_MAP();
    if (Default_Count == 0)
    {
        /* 틀린 갯수가 0개일 때. */
        /* 정답맵과 현재 맵 상태가 동일해 진 경우를 의미. */
        Answer_Cnt = Cnt;
        for (int i = 0; i < Cnt; i++)
        {
            int RC = Process[i][0];
            int Idx = Process[i][1];
            int M_Cnt = Process[i][2];
 
            Answer_Process[i][0] = RC;
            Answer_Process[i][1] = Idx;
            Answer_Process[i][2] = M_Cnt;
        }
        return;
    }
 
    /* 틀린 갯수를 통해서 앞으로 움직여야 할 횟수를 예측. */
    int Candidate_Change = Default_Count / 4;
    if (Default_Count % 4 != 0) Candidate_Change++;
    /* 틀린 갯수가 항상 4의 배수는 아니다. */
    /* 그런 경우에는 돌려야 할 예측 횟수를 + 1*/
 
    int Possible = Cnt + Candidate_Change;
    if (Possible >= Answer_Cnt) return;
    /* 앞으로 돌려야할 예측횟수가 기존의 정답보다 더 큰 값이라면 */
    /* 해당 경우는 더 이상 탐색해 볼 필요가 없다. */
 
    /* 그게 아니라면, 행과 열을 돌아가면서 모두 바꿔보기. */
    for (int k = 1; k <= 2; k++)
    {
        for (int i = 0; i < 4; i++)
        {
            for (int j = 1; j <= 3; j++)
            {
                Process[Cnt][0] = k;
                Process[Cnt][1] = i + 1;
                Process[Cnt][2] = j;
                
                Make_State(k, i, j, true);
                DFS(Cnt + 1);
                Make_State(k, i, j, false);
            }
        }
    }
}
 
void Solution()
{
    DFS(0);
    cout << Answer_Cnt << endl;
    for (int i = 0; i < Answer_Cnt; i++)
    {
        cout << Answer_Process[i][0] << " " << Answer_Process[i][1] << " " << Answer_Process[i][2] << 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;
}