[BOJ] 백준 2549 루빅의 사각형

출처: https://www.acmicpc.net/problem/2549

 Input 

1 2 15 4

7 8 3 6

9 10 5 12

13 14 11 16

 

 Output 

2

2 3 3

1 2 2

문제에서 정의한 한번의 움직임은 3가지 움직임을 의미합니다.

1칸 회전 = 2칸 회전 = 3칸 회전 = 한번의 움직임

따라서 매 단계 선택할 수 있는 경우의 수는

→ (행 4 + 열 4) * 회전 3가지(1, 2, 3) = 24가지

    ※ 회전의 경우 4cylce 주기를 갖고 있음

주어진 회전 횟수는 최대 7번 이므로 247이며, 16개 타일이 맞는 위치에 있는지 확인해야 하므로

→ O(247 * 16) = O(73,383,542,784)

    완전 탐색으로 이 모든 경우를 구현한다면 TLE 발생

따라서, 전체 경우를 살피는 과정에서 가능성이 없을 것 같은 경우는 끝까지 탐색하지 않고 중간에 걸러내야 합니다.

 

* 한번의 움직임으로 숫자들은 원래 숫자판에서 최대 4개 단위로 숫자가 달라집니다.

첫번째 행을 한 칸 회전했을 때) 4개의 숫자가 달라짐

첫번째 행 1칸 회전 + 첫번째 열 1칸 회전) 7개의 숫자가 달라짐

(diff + 3) / 4 만큼 움직여서 반드시 제위치로 돌아간다는 말은 아닙니다.

① 첫 번째 행 오른쪽 한 칸 이동

② 첫 번째 열을 아래오 한칸 이동

③ 첫 번째 행을 오른쪽으로 2칸 이동

▶ 제위치와 다른 갯수가 7개임에도 불구하고 3번의 움직임이 필요합니다.

따라서 만약 다른 개수(diff)가 7개이면 "2번의 움직임 필요"가 아닌 "최소 2번의 움직임 필요"로 생각합니다.

 

탐색과정에서 걸러내야 하는 부분은 현재 남은 움직임 횟수로 완성 가능성이 없는 경우만 제외합니다.

ex) 앞으로 움직이는 횟수가 2번 남았는데, 제자리에 있지 않은 숫자 개수(diff)가 9개 이상이면

    최소 3번의 움직임이 필요한 것이므로 계속해서 탐색할 필요가 없습니다.

    또한, 틀린 개수(diff)가 7여도 2번의 움직임으로 반드시 완성하는 것은 아니지만 탐색은 해보아야 하는것입니다

▶ rubic(lev, row, col) = lev단계에서 row행(col열)부터 회전

    diff = 자리에 맞지 않은 숫자의 개수

    적어도 (diff+3) / 4만큼은 돌려야 다 맞출 수 있다.

    그렇기에 ans ≤ lev + (diff + 3) / 4인 경우 가능성 X

 

 

※ 1번 행  → 3번 행 순서로 움직이나, 3번  → 1번 행 순서로 움직이든 결과는 같습니다.

    즉, 행을 연속하여 돌리거나 열을 연속하여 돌리는 것과 같이 순서때문에 결과가 달라지지 않습니다.

    (중복 없는 조합 개념과 비슷하다 (작은 숫자가 앞에 오도록하여 처리할 수 있습니다.))

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
int arr[4][4], ans = 8;
int rc[10], nth[10], rotCnt[10];
 
void input() {
    for (int i = 0; i < 4; ++i)
        for (int j = 0; j < 4; ++j) 
            scanf("%d", arr[i] + j);
}
 
void rotateCol(int j) {
    int t = arr[3][j];
    for (int i = 3; i > 0; --i)
        arr[i][j] = arr[i - 1][j];
    arr[0][j] = t;
}
 
void rotateRow(int i) {
    int t = arr[i][3];
    for (int j = 3; j > 0; --j)
        arr[i][j] = arr[i][j - 1];
    arr[i][0] = t;
}
 
int rubic(int lev, int r, int c) {
    int diff = 0, i, j;
    for (i = 0; i < 16; ++i)
        diff += arr[i / 4][i % 4] != i + 1;
 
    if (ans <= lev + (diff + 3) / 4)
        return 0;
 
    if (diff == 0) {
        ans = lev;
        return 1;
    }
 
    int rv = 0;
    // Rotate Row
    for (i = r; i < 4; ++i) {
        for (j = 1; j <= 3; ++j) { // 회전 3가지
            rotateRow(i);
            if (rubic(lev + 1, i + 1, 0)) {
                rc[lev] = 1, nth[lev] = i + 1, rotCnt[lev] = j;
                rv = 1;
            }
        }
        // 한번 더 돌려서 총 4번 돌린 상태로 만들어 기존 상태로 복원
        rotateRow(i);
    }
 
 
    // Rotate Col
    for (i = c; i < 4; ++i) {
        for (j = 1; j <= 3; ++j) {
            rotateCol(i);
            if (rubic(lev + 1, 0, i + 1)) {
                rc[lev] = 2, nth[lev] = i + 1, rotCnt[lev] = j;
                rv = 1;
            }
        }
        rotateCol(i);
    }
    return rv;
}
 
void output() {
    printf("%d\n", ans);
    for (int i = 0; i < ans; ++i)
        printf("%d %d %d\n", rc[i], nth[i], rotCnt[i]);
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
 
    rubic(0, 0, 0);
 
    output();
}