[BOJ] 16895번 Maaaaaaaaaze

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

16985번: Maaaaaaaaaze

문제

5 * 5 * 5 3차원 큐브를 각 층을 시계, 반시계 방향으로 회전시키고, 쌓아서 끝에서 끝으로 이동하는 최단거리를 구하는 문제이다. 

 

 

 

 

풀이

이 문제는 문항이 길고 시뮬레이션 + BackTraking + BFS를 조합한 문제로 삼성 SW 역량테스트를 준비하기 아주 좋은 문제인듯...

 

1. 먼저 각 층을 회전한다. 각 층이 회전하는 경우가 4가지 이므로 4 ^ 5가지의 경우의 수가 나오겠으나..... 원순열을 구하는 원리를 생각해볼때 중복된 경우가 많이나온다. 따라서 맨 윗층을 고정시켜 주었다.
2. 모든 층을 회전시켜 줄 때마다, 쌓아준다. 쌓는 경우는 next_permutation을 이용하거나 BackTraking을 이용하여 순열을 구하여 쌓아주면 되겠다.
3. 이후에 입구가 (0,0,0),(0,0,4),(0,4,0),(0,4,4)인 경우로 나누어 BFS로 (4,4,4),(4,4,0),(4,0,4),(4,0,0)까지 가는 최단 거리를 구해주면 된다. 이때 이미 answer가 12인 경우에는 더 이상 최단 거리가 나올 수 없으므로 break를 걸어준다. 

 

 

실수 했던 부분

• 우선, 출발점이나 도착점이 0인 경우를 배제해 주지 않았다. 문제를 제대로 읽지 않아서 생긴 문제이다. 왜 계속 이런 실수를 할까..... 문제를 정확히 2번 읽고 모든 경우를 다 생각해야한다. 문제 오래 읽어서 손해볼 거 없으니 조급해하지 말것
• 그리고 정답을 내는덴 상관 없었지만, answer가 12일 경우 가지치기를 하지 않았다. 항상 최적화 염두하기.

 

 

 

 

 

#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
int arr[5][5][5];
int cnt = 0;
int rotateResult[5][5][5];
int maze[5][5][5];
bool visited[5][5][5];
int a[5];
int answer = 5 * 5 * 5;
int dy[6] = { 0, 0, -1, 1, 0, 0 };
int dx[6] = { -1, 1, 0, 0, 0, 0 };
int dz[6] = { 0, 0, 0, 0, -1, 1 };

struct Point {
	int y;
	int x;
	int z;
};

void bfs(int sy, int sx, int sz, int ey, int ex, int ez) {
	if (maze[sy][sx][sz] == 0 || maze[ey][ex][ez] == 0) return;

	queue<Point> q;
	q.push({ sy,sx,sz });
	visited[sy][sx][sz] = true;
	
	int t = -1;
	while (!q.empty()) {
		t++;
		int sze = q.size();
		for (int j = 0; j < sze; j++) {
			int currY = q.front().y;
			int currX = q.front().x;
			int currZ = q.front().z;
			q.pop();

			if (currY == ey && currX == ex && currZ == ez) {
				answer = (answer < t) ? answer : t;
				return;
			}

			for (int i = 0; i < 6; i++) {
				int nextY = currY + dy[i];
				int nextX = currX + dx[i];
				int nextZ = currZ + dz[i];


				if (nextY < 0 || nextX < 0 || nextZ < 0 || nextY > 4 || nextX > 4 || nextZ > 4) continue;
				if (visited[nextY][nextX][nextZ]) continue;
				if (maze[nextY][nextX][nextZ] == 0) continue;

				q.push({ nextY, nextX, nextZ });
				visited[nextY][nextX][nextZ] = true;
			}
		}
	}
	
}

void pile() {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			for (int k = 0; k < 5; k++) {
				maze[a[i]][j][k] = rotateResult[i][j][k];
			}
		}
	}
}

void init() {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			for (int k = 0; k < 5; k++) {
				visited[i][j][k] = false;
			}
		}
	}
}

void rotate(int i, int d) {
	if (d == 0) {
		for (int j = 0; j < 5; j++) {
			for (int k = 0; k < 5; k++) {
				rotateResult[i][j][k] = arr[i][j][k];
			}
		}
	}
	else if (d == 1) {
		for (int j = 0; j < 5; j++) {
			for (int k = 0; k < 5; k++) {
				rotateResult[i][j][k] = arr[i][4 - k][j];
			}
		}
	}
	else if (d == 2) {
		for (int j = 0; j < 5; j++) {
			for (int k = 0; k < 5; k++) {
				rotateResult[i][j][k] = arr[i][4 - j][4 - k];
			}
		}
	}
	else if (d == 3) {
		for (int j = 0; j < 5; j++) {
			for (int k = 0; k < 5; k++) {
				rotateResult[i][j][k] = arr[i][k][4 - j];
			}
		}
	}
}

int main() {
	//입력
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			for (int k = 0; k < 5; k++) {
				cin >> arr[i][j][k];
			}
		}
	}

	//회전
	
    bool flag = false;
	rotate(0, 0);
	for (int j = 0; j < 4; j++) {
		rotate(1, j);
		for (int k = 0; k < 4; k++) {
			rotate(2, k);
			for (int l = 0; l < 4; l++) {
				rotate(3, l);
				for (int m = 0; m < 4; m++) {
					rotate(4, m);
					//쌓는다.
					for (int i = 0; i < 5; i++) a[i] = i;
					do {
						//쌓는다.
						pile();
						//입구, 출구 정한다.
						bfs(0, 0, 0, 4, 4, 4);
						if (answer == 12) {
                            flag = true;
                            break;
                        }
						init();
						bfs(0, 4, 0, 4, 0, 4);
						if (answer == 12) {
                            flag = true;
                            break;
                        }
						init();
						bfs(4, 0, 0, 0, 4, 4);
						if (answer == 12) {
                            flag = true;
                            break;
                        }
						init();
						bfs(4, 4, 0, 0, 0, 4);
						if (answer == 12) {
                            flag = true;
                            break;
                        }
						init();
					} while (next_permutation(a, a + 5));
                    if(flag) break;
				}
                if(flag) break;
			}
            if(flag) break;
		}
        if(flag) break;
	}
	
	if (answer == 5 * 5 * 5) cout << -1;
	else cout << answer;
}