5 Problem C : 루빅의 사각형

4*4 격자판에 1~16까지 정수 번호가 매겨진 16개 타일

타일을 정사정적으로 돌려 놓기 위해 타일을 움직이는 순서를 출력하는 프로그램을 작성

 

- dfs

- 가치치기

  - 완성하기 위한 step 이 존재하는데, 최소한 몇 개는 맞아야 한다, 아닌 경우 return

 

- dfs() : step 을 파라미터로 받음

- okcnt() : 현재까지 돌린 타일과 정상 타일과 비교해서 몇 개나 맞는지 확인

- rotate() : 배열 이동하는 것 간편하게 함수 만들음

 

#include <stdio.h>

int tile[6][6], ans = 8;
struct data {
	int rc, num, cnt;
} moving[10], moveans[10];

// 원하는 그림과 얼마나 같은지 
int okcnt()
{
	int cnt = 0;
	for (int i = 1, k = 1; i <= 4; i++)
		for (int j = 1; j <= 4; j++)
			cnt += tile[i][j] == k++;
	return cnt;
}

void rotate(int rc, int num)
{
	int tmp, i;
	if (rc == 1) {
		tmp = tile[num][4];
		for (i = 4; i > 1; i--) tile[num][i] = tile[num][i - 1];
		tile[num][1] = tmp;
	}
	else {
		tmp = tile[4][num];
		for (i = 4; i > 1; i--) tile[i][num] = tile[i - 1][num];
		tile[1][num] = tmp;
	}
}

void dfs(int step)
{
	int ok = okcnt(), i, j, k;
	if (ok == 16) { // 원하는 그림이 나옴
		ans = step;
		for (i = 0; i < ans; i++) moveans[i] = moving[i];
		return;
	}
	if (ok < (step + 5 - ans) * 4) return; // 맞춰야 할 숫자가 남은 step 안에 못 맞출 경우 return
	for (i = 1; i <= 2; i++) {
		for (j = 1; j <= 4; j++) {
			for (k = 1; k < 4; k++) {
				moving[step] = { i, j, k };
				rotate(i, j);
				dfs(step + 1);
			}
			rotate(i, j);
		}
	}
}

int main()
{
	for (int i = 1; i <= 4; i++)
		for (int j = 1; j <= 4; j++)
			scanf("%d", &tile[i][j]);

	dfs(0);
	printf("%d\n", ans);
	for (int i = 0; i < ans; i++)
		printf("%d %d %d\n", moveans[i].rc, moveans[i].num, moveans[i].cnt);
	return 0;
}

1 2 15 4 7 8 3 6 9 10 5 12 13 14 11 16

2 2 3 3 1 2 2