[백준 16985] Maaaaaaaaaze

https://www.acmicpc.net/problem/16985

16985번: Maaaaaaaaaze

#include <cstdio>
#include <cstring>
#include <queue>
int maze[5][5][5];
int board[5][5][5];		//in-data
int choice[5];			//permu
int ans = 0x7fffffff;

struct _st
{
	int z, x, y;
};
std::queue<_st> Q;
int visited[5][5][5];

_st in_point[4] = { {0, 0, 0}, {0, 0, 4}, {0, 4, 0}, {0, 4, 4}};
_st out_point[4] = { {4, 4, 4}, {4, 4, 0}, {4, 0, 4}, {4, 0, 0}};


void input()
{
	for (int h = 0; h < 5; h++) {
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				scanf("%d", &board[h][i][j]);
			}
		}
	}
}

int BFS(int p)
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };
	static int dir_z[2] = { -1, 1 };

	Q = {};
	memset(visited, 0, sizeof(visited));

	Q.push({ in_point[p].z, in_point[p].x, in_point[p].y });
	visited[in_point[p].z][in_point[p].x][in_point[p].y] = 1;
	//printf("%d %d %d %d %d %d\n", in_point[p].z, in_point[p].x, in_point[p].y, out_point[p].z, out_point[p].x, out_point[p].y);

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		if (data.x == out_point[p].x && data.y == out_point[p].y && data.z == out_point[p].z) {
			return visited[out_point[p].z][out_point[p].x][out_point[p].y] - 1;
		}

		// 같은 층, 너비 탐색
		for (int d = 0; d < 4; d++) {
			int nx = data.x + dir_x[d];
			int ny = data.y + dir_y[d];
			if (nx < 0 || nx > 4 || ny < 0 || ny > 4) continue;
			if (visited[data.z][nx][ny]) continue;
			if (maze[data.z][nx][ny] == 0) continue;
			Q.push({ data.z, nx, ny });
			visited[data.z][nx][ny] = visited[data.z][data.x][data.y] + 1;
		}
		// 다른 층 탐색 
		for (int d = 0; d < 2; d++) {
			int nz = data.z + dir_z[d];
			if (nz < 0 || nz > 4) continue;
			if (visited[nz][data.x][data.y]) continue;
			if (maze[nz][data.x][data.y] == 0) continue;
			Q.push({ nz, data.x, data.y });
			visited[nz][data.x][data.y] = visited[data.z][data.x][data.y] + 1;
		}
	}
	return -1;
}


void CW90(int n, int idx)
{
	memset(maze[n], 0, sizeof(maze[n]));
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			maze[n][i][j] = board[idx][5 - j - 1][i];
		}
	}
}



void CW180(int n, int idx)
{
	memset(maze[n], 0, sizeof(maze[n]));
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			maze[n][i][j] = board[idx][5 - i - 1][5 - j - 1];
		}
	}
}

void CW270(int n, int idx)
{
	memset(maze[n], 0, sizeof(maze[n]));
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			maze[n][i][j] = board[idx][j][5 - i - 1];
		}
	}
}



void make_pann(int n, int idx, int r)
{
	if (r == 0) {
		memset(maze[n], 0, sizeof(maze[n]));
		memcpy(maze[n], board[idx], sizeof(maze[n]));
	}
	else if (r == 1) CW90(n, idx);
	else if (r == 2) CW180(n, idx);
	else if (r == 3) CW270(n, idx);
}




void DFS(int n)	// maze의 n번째 칸 만들것임 
{
	if (n == 5) {
		for (int p = 0; p < 4; p++) {	// 4개의 꼭짓점이 입구가 될 수 있음
			if (maze[in_point[p].z][in_point[p].x][in_point[p].y] == 0) continue;
			if (maze[out_point[p].z][out_point[p].x][out_point[p].y] == 0) continue;
			int move = BFS(p);
			if (move != -1 && move < ans) {
				ans = move;
				//debug();
			}
		}
		return;
	}


	// 어차피 층마다 판을 붙이기 때문에 맵을 백업받고 복원해줄 필요 없음 

	for (int i = 0; i < 5; i++) {		// 몇번째 판 
		if (choice[i]) continue;
		for (int r = 0; r < 4; r++) {	// 몇번 돌릴 것인지 
			choice[i] = 1;
			make_pann(n, i, r);			// maze의 n번째 판에 board의 i번째 판을 r번 돌려서 넣는다 
			DFS(n + 1);
			choice[i] = 0;		
		}
	}
}



int main()
{
	input();
	DFS(0);	// 몇번째 칸 만드는건지
	if (ans == 0x7fffffff) printf("%d\n", -1);
	else printf("%d\n", ans);
	return 0;
}

1. (0, 0, 0)에서 출발해서 (4, 4, 4)로 나오나, (4, 4, 4)에서 출발해서 (0, 0, 0)으로 나오나 똑같다.

그래서 in / out 꼭짓점 정해서 BFS 돌릴 때 8번이 아니라 그 절반만 돌려줘도 된다. 이것 때문에 처음에 타임아웃 났었다.

 

2. 이 문제는 DFS를 돌면서 maze라는 3차원 배열을 층층이 쌓아서 간다. (배열을 수정해주지 않음)

따라서 DFS 진행 중에 맵을 백업 / 복원하는 절차가 필요하지 않다.