알고리즘 :: 백준 :: 시뮬레이션 :: 1917 :: 정육면체 전개도

문제

문제접근

문제 이해

• 정말 까다로운 문제입니다.
  만일 정육면체 전개도 종류가 11가지라는 사실을 몰랐다면 이 문제를 어떻게 풀 수 있을지 모르겠습니다.

• 중앙 파란색 전개도를 제외한 나머지 10가지 전개도는 3X4 배열로 나타낼 수 있습니다.
  (중앙 파란색 전개도는 2x5 배열로 나타내야 ㄴ합니다.)

• True와 False를 이용해서 전개도를 나타내봅시다.

  

• 이제 문제에서 주어지는 6x6 배열의 모든 칸에 대해 정육면체 전개도를 하나씩 대보면서 검사합니다.

• 이때 검사할 때는 매 전개도마다 반전 2회, 회전 4회를 적용해서 총 8번 검사합니다.

• 모든 좌표마다 $8 \times (3 \times 4) = 96$번 검사하고 좌표는 36개 있으므로 총 $3,456$번만 검사하면 됩니다.

코드

#include <iostream>
#include <vector>
using namespace std;

const vector<vector<string>> cubes = {
	{"0010", "1111", "0010"},
    {"0100", "1111", "1000"},
    {"0010", "1111", "0100"},
    {"0001", "1111", "1000"},
    {"0001", "1111", "0100"},
    {"11100", "00111"},
    {"1100", "0111", "0010"},
    {"1100", "0111", "0001"},
    {"0010", "1110", "0011"},
    {"0001", "1111", "0001"},
    {"1100", "0110", "0011"}
};
constexpr int T = 3, N = 6;
vector<vector<int>> a(N, vector<int>(N));

vector<string> mirror(const vector<string>& cube) {
	int row = cube.size(), col = cube[0].length();
	vector<string> ret(cube.size());
	for (int y = 0; y < row; ++y)
		for (int x = col - 1; x >= 0; --x)
			ret[y] += cube[y][x];
	return ret;
}

vector<string> rotate(const vector<string>& cube) {
	int row = cube[0].length(), col = cube.size();
	vector<string> ret(row);
	for (int y = 0; y < row; ++y)
		for (int x = col - 1; x >= 0; --x)
			ret[y] += cube[x][y];
	return ret;
}

bool check(const vector<string>& cube, int y, int x) {
	for (int i = 0; i < cube.size(); ++i)
		for (int j = 0; j < cube[0].length(); ++j) {
			int ny = y + i, nx = x + j;
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) return false;
			if ((cube[i][j] - '0') != a[ny][nx]) return false;
		}
	return true; 
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	for (int i = 0; i < T; ++i) {
		for (int y = 0; y < N; ++y)
			for (int x = 0; x < N; ++x)
				cin >> a[y][x];
		bool ans = false;
		vector<string> cube;
		for (const auto& c : cubes) {
			cube = c;
			for (int mir = 0; mir < 2; ++mir) {
				for (int rot = 0; rot < 4; ++rot) {
					for (int y = 0; y < N; ++y)
						for (int x = 0; x < N; ++x)
							ans |= check(cube, y, x);
					cube = rotate(cube);
				}
				cube = mirror(cube);
			}
		}
		cout << (ans ? "yes" : "no") << '\n';
	}
}

결과