[백준/BOJ] 백준 16985번 : Maaaaaaaaaze

www.acmicpc.net/problem/16985

16985번: Maaaaaaaaaze

각각 보드를 돌렸을 상황에 대해서 보드를 쌓는 경우를 모두 고려하여 문제를 해결했다. boards의 각 칸은 boards[z][x][y]를 나타낸다.

 

코드

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

int boards[5][5][5];
int dxdy[6][3] = { {1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1} }; //z,x,y;
int result = 987654321;
struct point {
	int z;
	int x;
	int y;
};

//turn_check보드를 돌린다
void Turn(int turn_check)
{
	int temp_board[5][5];

	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
		{
			temp_board[i][j] = boards[turn_check][4 - j][i];
		}

	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			boards[turn_check][i][j] = temp_board[i][j];
}

//order 순서로 블록을 쌓았을때 이동횟수 구하기
int Move(vector<int> order)
{
	int maked_board[5][5][5];

	for (int k = 0; k < order.size(); k++)
	{
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 5; j++)
				maked_board[k][i][j] = boards[order[k]][i][j];
	}

	point start = { 0,0,0 };
	point dest = { 4,4,4 };

	//시작지 또는 목적지를 들어갈 수 없을때
	if (maked_board[start.z][start.x][start.y] == 0 || maked_board[dest.z][dest.x][dest.y] == 0)
		return 987654321;

	int discovered[5][5][5];
	int depth[5][5][5];
	queue<point> q;

	for (int k = 0; k < 5; k++)
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 5; j++)
				discovered[k][i][j] = 0;


	discovered[start.z][start.x][start.y] = 1;
	depth[start.z][start.x][start.y] = 0;
	q.push(start);

	while (!q.empty())
	{
		point here = q.front();
		q.pop();

		//목적지에 도달 했을때
		if (here.z == dest.z && here.x == dest.x && here.y == dest.y)
			return depth[here.z][here.x][here.y];

		for (int i = 0; i < 6; i++)
		{
			point there = { here.z + dxdy[i][0], here.x + dxdy[i][1], here.y + dxdy[i][2] };

			if (there.x >= 0 && there.y >= 0 && there.z >= 0 && there.x < 5 && there.y < 5 && there.z < 5 && discovered[there.z][there.x][there.y] == 0 && maked_board[there.z][there.x][there.y] == 1)
			{
				discovered[there.z][there.x][there.y] = 1;
				depth[there.z][there.x][there.y] = depth[here.z][here.x][here.y] + 1;
				q.push(there);
			}
		}
	}

	return 987654321;
}

void Solve(int turn_check)
{
	//모든 보드 돌리는 경우를 고려 했을때
	if (turn_check == 5)
	{
		vector<int> order;
		for (int i = 0; i < 5; i++)
			order.push_back(i);
		//order는 정렬 되어 있다

		do {
			result = min(result, Move(order));
		} while (next_permutation(order.begin(), order.end())); //보드를 쌓는 모든 경우를 고려한다

		return;
	}

	for (int i = 0; i < 4; i++)
	{
		Solve(turn_check + 1);
		Turn(turn_check); //turn_check 보드를 돌린다 4번 돌면 원래대로 돌아온다
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	for (int k = 0; k < 5; k++)
	{
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 5; j++)
			{
				int input;
				cin >> input;

				boards[k][i][j] = input;
			}
	}

	Solve(0);

	if (result == 987654321)
		cout << -1;
	else
		cout << result;

	return 0;
}