BOJ 16985: Maaaaaaaaaze

#BOJ 16985: Maaaaaaaaaze

16985번: Maaaaaaaaaze

#풀이

최단거리를 구하기 - bfs

5층의 배열[5][5] 쌓기 - 백트래킹

90도 회전 - 백트래킹

 

문제를 풀면서 백트래킹을 이용하여 풀었는데 인덱스를 제대로 확인하지 않아 정말 오래걸렸다......

인덱스 확인 꼭! 잘해야해!!

문제가 3차원배열로 풀어서 디버깅을 할 때도 너무 불편했다.

 

#코드

#include<iostream> //#include<bits/stdc++.h>
#include<queue>
using namespace std;
int board[5][5][5];
int board2[5][5][5];

int vis_stack[5];
int dx[6] = { 1, -1, 0, 0, 0, 0 };
int dy[6] = { 0, 0, 1, -1, 0, 0 };
int dz[6] = { 0, 0, 0, 0, 1, -1 };
queue<pair<pair<int, int>, int>> q; // x,y,z
int ans;
void func_rot(int arr[][5]) { // 90도 판회전  1: 90 2: 180  3: 270  4 : 360
	int rotarr[5][5];
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			rotarr[i][j] = arr[4 - j][i];
		}
	}
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			arr[i][j] = rotarr[i][j];
		}
	}
}
void bfs() {// 출구까지 최단 거리 구하기
	int vis[5][5][5] = { 0, };
	if (board2[4][4][4] == 1 && board2[0][0][0] == 1)
	{
		q.push({ {0, 0}, 0 });
		vis[0][0][0] = 1;
		while (!q.empty()) {
			auto a = q.front(); q.pop();
			for (int i = 0; i < 6; i++) {
				int x = a.first.first + dx[i];
				int y = a.first.second + dy[i];
				int z = a.second + dz[i];
				if (x < 0 || y < 0 || z < 0 || x >= 5 || y >= 5 || z >= 5 || vis[x][y][z] != 0 || board2[x][y][z] == 0)
					continue;
				q.push({ {x,y},z });
				vis[x][y][z] = vis[a.first.first][a.first.second][a.second] + 1;
			}
		}
	}
	if (ans <= 0) {
		ans = vis[4][4][4] == 0 ? -1 : vis[4][4][4];
	}
	else if (ans > 0) {
		if(vis[4][4][4] != 0)
			ans = ans > vis[4][4][4] ? vis[4][4][4] : ans;
	}
}
int ss[5];
int sss[5];
void func_stack(int k) { // 5개의 큐브 쌓기
	if (k == 5) {
		bfs();
		return;
	}

	for (int i = 0; i < 5; i++) {
		if (vis_stack[i] == 1)
			continue;
		vis_stack[i] = 1;
		for (int j = 1; j <= 4; j++) {
			func_rot(board[i]);
			for (int x = 0; x < 5; x++) {
				for (int y = 0; y < 5; y++) {
					board2[k][x][y] = board[i][x][y];
				}
			}
			ss[k] = i;
			sss[k] = j;
			func_stack(k+1);
		}
		vis_stack[i] = 0;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			for (int k = 0; k < 5; k++) {
				cin >> board[i][j][k];
			}
		}
	}
	func_stack(0);
	ans = ans == -1 ? ans : ans - 1;
	cout << ans<< '\n';
	return 0;
}