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

문제 링크: https://www.acmicpc.net/problem/2549

2549번: 루빅의 사각형

1. 주의할 점

- 푸는 방법이 여러가지 존재하지만, 여기서는 백트레킹을 활용해서 해결한다

- 한 열/행을 1~3칸 이동하는것은 전부 1번 옮긴것과 같다

 

2. 구현

- 현재 배열의 상태(Arr[][])와 최종적으로 원하는 배열의 상태(Corr[][])를 비교하여 틀린 개수를 반환하는 Cal()

함수를 구현한다

- Cal() 함수를 통해 다른 개수를 반환 받은 후, 다음과 같은 가정을 할 수 있다(이 부분이 가장 중요)

(1) 만약 일치하지 않는 개수(Dismatch)가 4의 배수라면 적어도 (Dismatch/4)번의 열/행을 회전시키면 Corr[][]와 일치하지 않을까?

(2) 만약 일치하지 않는 개수가 4의 배수가 아니라면 (Dismatch/4)보다 큰 자연수번의 열/행을 회전시키면 Corr[][]와 일치하지 않을까?

- 위에서 말하는 적어도 ~~번을 Maybe라는 변수에 담아두고, Maybe+현재 이동한 횟수가 이미 구한 횟수보다 크거나 같다면 확일할 필요가 없다

- 'Maybe+현재 이동횟수 < 이미 구한 정답(Result)' 을 만족한다면 모든 행/열에 대하여(2*4) 1~3칸씩 움직이는(3) 모든 경우의 수를 해본다(총 24가지의 경우)

- 단, MV() 함수를 통해 Arr[][] 배열을 바꾸고 DFS()를 실행시켰다면, 돌아왔을때는 이전의 Arr[][]값을 가져야 하므로 따로 처리한다(DFS의 기본)

 

#include <iostream>
using namespace std;
int ans[7][3], t_ans[7][3], result = 8;
int arr[5][5], corr[5][5];

int cal() {
	int t = 0;
	for (int i = 1; i < 5; i++)
		for (int j = 0; j < 5; j++)
			if (arr[i][j] != corr[i][j])
				t++;
	return t;
}

void mv(int cnt) {
	if (t_ans[cnt][0] == 1) {		//오른쪽으로 이동
		int idx = t_ans[cnt][1];
		for (int t = 0; t < t_ans[cnt][2]; t++) {		//t칸 오른쪽으로 이동
			int temp = arr[idx][4];
			arr[idx][4] = arr[idx][3];
			arr[idx][3] = arr[idx][2];
			arr[idx][2] = arr[idx][1];
			arr[idx][1] = temp;
		}
	}
	else {			//밑으로 이동
		int idx = t_ans[cnt][1];
		for (int t = 0; t < t_ans[cnt][2]; t++) {		//t칸 밑으로 이동
			int temp = arr[4][idx];
			arr[4][idx] = arr[3][idx];
			arr[3][idx] = arr[2][idx];
			arr[2][idx] = arr[1][idx];
			arr[1][idx] = temp;
		}
	}
}

void dfs(int cnt) {
	int dismatch = cal();
	if (dismatch == 0) {		//안바꿔도 이미 정답인 경우
		result = cnt;
		for (int i = 0; i < cnt; i++) {
			ans[i][0] = t_ans[i][0];
			ans[i][1] = t_ans[i][1];
			ans[i][2] = t_ans[i][2];
		}
		return;
	}
	int maybe;
	if (dismatch % 4 == 0) maybe = dismatch / 4;
	else maybe = dismatch / 4 + 1;
	if (cnt + maybe >= result) return;		//적어도 저만큼 돌려야하는데 이미 구한값이 저거보다 적은 경우
	for (int j = 1; j < 3; j++) {		//행or열
		for (int i = 1; i < 5; i++) {		//몇번째(1~4)
			for (int k = 1; k < 4; k++) {		//몇칸 이동
				t_ans[cnt][0] = j;
				t_ans[cnt][1] = i;
				t_ans[cnt][2] = k;
				mv(cnt);
				dfs(cnt + 1);
				t_ans[cnt][2] = 4 - k;
				mv(cnt);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int num = 1;
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= 4; j++) {
			cin >> arr[i][j];
			corr[i][j] = num++;
		}
	}
	
	dfs(0);
	cout << result << '\n';
	for (int i = 0; i < result; i++) {
		cout << ans[i][0] << " " << ans[i][1] << " " << ans[i][2] << '\n';
	}
	system("pause");
	return 0;
}