[백준 16939] 2x2x2 큐브

문제링크 : 바로가기

16939번: 2×2×2 큐브

 

큐브를 한 번만 돌려서 모든 면을 맞출 수 있는지 확인하는 문제이다.

배열 돌리는 연산을 구현하는 것이 살짝 까다롭다. 
큐브는 3차원이기 때문에 돌리는 방향은 3가지로 표현 할 수 있다. 전개도를 고정하고 돌릴 수 있는 방향을 써보면 위, 아래( == 위 x3 == -위), 왼쪽, 오른쪽( == 왼쪽 x3 == -왼쪽), 시계방향, 반시계방향(== 시계방향 x3 == -시계방향)이다.

 

1. 위쪽 방향

 

 

2. 왼쪽 방향

 

 

 

3. 반시계 방향

 

 

1번에서 위쪽 방향으로 돌릴 때 맨 오른쪽 (노란색, 회색)인 칸도 움직이어야한다. 이에 대해 편하게 코딩하기 위해 아래와 같이 만들고 코딩을 하였다.

 

맨 오른쪽에 있었던 것을 좌우대칭을 하여 맨 아래에 추가하면 된다. 따라서 8 x 8 배열을 가지고 큐브 정보를 가지고 있으면 편리하게 코딩을 할 수 있다. 

 

위 방향으로 돌리는 것과 왼쪽 방향으로 돌리는 것은 매우 쉽다. 하지만 시계방향, 반시계방향은 간단하게 짜려다 돌리는 걸 못해 그냥 구현하였다.

 

#include<bits/stdc++.h>

using namespace std;

int Map[8][8], color[25];

void init(){
	int number = 0;
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 2; j++) {
			int y = i;
			int x = j + 2;
			Map[y][x] = color[++number];
		}
	}

	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			int y = 2 + i;
			int x = j;
			Map[y][x] = color[++number];
		}
	}

	for (int k = 0; k < 2; k++) {
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				int y = 2 + i;
				int x = 4 + 2 * k + j;
				Map[y][x] = color[++number];
				if (k == 1) {
					Map[6 + i][3 - j] = Map[y][x];
				}
			}
		}
	}
}

void up(int line) { 
	for (int i = 0; i < 2; i++) {
		int temp = Map[i][line];
		for (int j = 1; j <= 3; j++) {
			Map[2 * j - 2 + i][line] = Map[j * 2 + i][line];
		}
		Map[6 + i][line] = temp;
	}
}

void left(int line) { 
	for (int i = 0; i < 2; i++) {
		int temp = Map[line][i];
		for (int j = 1; j <= 3; j++) {
			Map[line][i + 2 * j - 2] = Map[line][i + 2 * j];
		}
		Map[line][6 + i] = temp;
	}
}

void rotate(int line) {
	int dx[] = { 2,1,-2,-1 };
	int dy[] = { 1,-2,-1,2 };
	if (!line) {
		for (int k = 0; k < 4; k++) {
			if (dx[k] < 0)dx[k]--;
			else dx[k]++;
			if (dy[k] < 0)dy[k]=--dy[k] * -1;
			else dy[k]=++dy[k] * -1;
		}
	}
	for (int i = 0; i < 2; i++) {
		int temp = Map[2 + i][line];
		int y = 2 + i, x = line;
		if (i) {
			for (int k = 0; k < 4; k++) {
				swap(dy[k], dx[k]);
				if (dy[k] * dx[k] < 0) {
					dy[k] *= -1;
					dx[k] *= -1;
				}
			}
		}
		for (int j = 0; j < 3; j++) {
			int ny = y + dy[j];
			int nx = x + dx[j];
			Map[y][x] = Map[ny][nx];
			y = ny; x = nx;
		}
		Map[y][x] = temp;
	}
}

bool check(bool left = false) {
	for (int k = 0; k < 3; k++) {
		for (int m = 0; m < 3; m++) {
			int temp = Map[k * 2][m * 2];
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 2; j++) {
					if (temp != Map[k * 2 + i][m * 2 + j])return false;
				}
			}
		}
	}

	int y = 6, x = 2;
	if (left)swap(x, y);

	int temp = Map[y][x];
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			if (temp != Map[y + i][x + j])return false;
		}
	}
	return true;
}

bool solve() {
	for (int i = 0; i < 2; i++) {
		up(2 + i); // first
		if (check())return true;
		for (int j = 0; j < 2; j++)up(2 + i);
		if (check())return true;
		up(2 + i);
	}

	for (int i = 0; i < 2; i++) {
		left(2 + i);
		if (check(true))return true;
		for (int j = 0; j < 2; j++)left(2 + i);
		if (check(true))return true;
		left(2 + i);
	}

	for (int i = 0; i < 2; i++) {
		rotate(i);
		if (check(true))return true;
		for (int j = 0; j < 2; j++)rotate(i);
		if (check(true))return true;
		rotate(i);
	}
	return false;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	for (int i = 1; i <= 24; i++)
		cin >> color[i];

	init();

	cout << solve() << '\n';

	return 0;
}