BOJ 11742 Hypercube

문제 링크입니다.

문제 요약

주어진 정팔포체의 전개도가 올바른지 판별합시다.

정육면체의 전개도로부터의 확장

정육면체의 전개도를 그리라 하면 저는 보통 이런 그림을 그립니다. 이 전개도를 접으면, 위아래의 면이 3, 4고 이를 둘러싸는 옆면이 1, 5, 6, 2인 육면체 주사위를 얻을 수 있습니다.

여기서, 옆면을 이루는 1, 5, 6, 2가 전개도 상에서 한 줄을 이루고 있음에 주목합시다. 이 줄은 접는 과정에서 3과 4를 따라 말리면 되는 것이므로, 이 줄을 다음 그림과 같이. 위아래로 당겨도 동일한 전개도임을 알 수 있습니다.

이를 역으로 생각하면, 전개도 위에서 위아래로 움직여도 양옆에 붙을 수 있는 칸은 고정되어 있게 됩니다. 이는 정팔포체의 전개도에서도 성립하는 성질입니다. 따라서, 각 칸에 적당히 번호를 붙이고 현재 칸에 붙을 수 있는 칸의 번호들을 관리하면서 그래프 탐색을 돌린 뒤, 모든 종류의 칸이 한 번씩 나타나는지만 확인해 주면 문제를 해결할 수 있습니다. 주사위처럼 마주보는 면(여기서는 정육면체가 하나의 면이겠네요.)에 적힌 수의 합을 일정하도록 수를 배치하면 구현이 좀 편합니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

char board[10][10][10];
bool vis[10][10][10];
int now[7][7][7];
int n, m, k;

set<int> st;

const int dx[] = {1,-1,0,0,0,0};
const int dy[] = {0,0,1,-1,0,0};
const int dz[] = {0,0,0,0,1,-1};

void solve(int x, int y, int z){
	st.insert(now[3][3][3]);
	vis[x][y][z] = 1;
	for(int d = 0; d < 6; d++){
		if(board[x+dx[d]][y+dy[d]][z+dz[d]] == '.') continue;
		if(vis[x+dx[d]][y+dy[d]][z+dz[d]]) continue;
		for(int i = 2; i >= -1; i--) now[3+i*dx[d]][3+i*dy[d]][3+i*dz[d]] = now[3+(i-1)*dx[d]][3+(i-1)*dy[d]][3+(i-1)*dz[d]];
		now[1][3][3] = now[5][3][3] = 9-now[3][3][3];
		now[3][1][3] = now[3][5][3] = 9-now[3][3][3];
		now[3][3][1] = now[3][3][5] = 9-now[3][3][3];
		solve(x+dx[d], y+dy[d], z+dz[d]);
		for(int i = 2; i >= -1; i--) now[3+i*dx[d^1]][3+i*dy[d^1]][3+i*dz[d^1]] = now[3+(i-1)*dx[d^1]][3+(i-1)*dy[d^1]][3+(i-1)*dz[d^1]];
		now[1][3][3] = now[5][3][3] = 9-now[3][3][3];
		now[3][1][3] = now[3][5][3] = 9-now[3][3][3];
		now[3][3][1] = now[3][3][5] = 9-now[3][3][3];
	}
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	memset(board, '.', sizeof(board));
	cin >> m >> n >> k;
	int sx, sy, sz;
	for(int z = 1; z <= k; z++) for(int y = 1; y <= n; y++) for(int x = 1; x <= m; x++){
		cin >> board[x][y][z];
		if(board[x][y][z] == 'x'){sx = x; sy = y; sz = z;}
	}
	now[3][3][3] = 1;
	now[4][3][3] = 2;
	now[3][4][3] = 3;
	now[3][3][4] = 4;
	now[3][3][2] = 5;
	now[3][2][3] = 6;
	now[2][3][3] = 7;
	now[1][3][3] = now[5][3][3] = 8;
	now[3][1][3] = now[3][5][3] = 8;
	now[3][3][1] = now[3][3][5] = 8;
	solve(sx, sy, sz);
	cout << (st.size() == 8 ? "Yes" : "No");
}