백준 16985 c++ "Maaaaaaaaaze" -PlusUltraCode-

백준/구현

백준 16985 c++ "Maaaaaaaaaze" -PlusUltraCode-

PlusUltraCode 2025. 7. 22. 09:43

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

[필자 사고]

구현 문제인데 종합 선물세트 같았다.

3차원 배열, 백트래킹, bfs탐색, 회전, 백트래킹 시 회전 관련 idx처리

과거동안 배워 온 탐색에서 필요한 알고리즘을 여기서 복습한 느낌이였다.

좋은 문제같다.

[코드 해설]

1. Rotate(vector<vector<int>> arr)

이 함수는 5×5 2차원 배열을 시계 방향으로 90도 회전한 새로운 배열을 만들어 반환합니다.
회전 결과는 새로운 배열에 저장되며, 기존 배열을 직접 수정하지 않습니다.
이 회전은 각 층의 회전 조합을 만들기 위해 사용됩니다.

2. RotateAndInputMap(vector<vector<int>>& arr, int mapCount)

이 함수는 하나의 층(5×5 배열)을 인자로 받아 해당 층을 0도, 90도, 180도, 270도로 회전한 결과를 myMap[mapCount]에 저장합니다.
즉, 각 층마다 4개의 회전된 버전을 미리 저장해두는 역할을 합니다.
mapCount는 해당 층의 고유 번호이며, 총 5개 층이 0번부터 4번까지 있습니다.

3. Input()

사용자로부터 5개의 5×5 미로 층을 입력받는 함수입니다.
각 층을 읽고 나면 RotateAndInputMap 함수를 통해 회전 버전까지 모두 저장합니다.
최종적으로 myMap에는 myMap[0]부터 myMap[4]까지, 각 층의 4가지 회전 결과가 들어 있습니다.

4. isInside(int sero, int garo, int height)

주어진 좌표 (y, x, z)가 미로 범위 5×5×5 안에 있는지 검사하는 함수입니다.
좌표가 0 이상 4 이하일 때만 true를 반환하며, BFS 중 경계 체크에 사용됩니다.

5. BFS(Idx idxS, Idx idxE)

3차원 미로에서 **시작점(idxS)**부터 **도착점(idxE)**까지 최단 경로를 찾는 너비 우선 탐색(BFS) 함수입니다.
미로는 resultMap에 구성되어 있고, 각 좌표가 1이면 길, 0이면 벽입니다.
6방향(동서남북상하)으로 이동하면서, 최소 이동 횟수를 구합니다.
시작점이나 도착점이 벽일 경우에는 -1을 반환하며 탐색을 건너뜁니다.
최종적으로 도착점에 도달하면 이동한 칸 수(거리)를 반환하고, 도달하지 못하면 -1을 반환합니다.

6. BackTracking(int depth)

이 함수는 층의 순서와 회전 상태를 조합하여 resultMap을 구성하는 역할을 합니다.
총 5개의 층을 선택하고, 각각의 층에 대해 4가지 회전 상태 중 하나를 적용합니다.
중요한 점은 같은 층이 두 번 쓰이면 안 되므로 used[i] 배열을 이용하여 중복을 방지합니다.
각 조합에 대해 resultMap이 완성되면, (0,0,0)에서 (4,4,4)까지의 최단 경로를 BFS()로 계산하고, 최솟값을 저장합니다.
총 5! * 4^5 = 122,880가지 조합을 모두 탐색합니다.

7. Game_Start()

이 함수는 미로 조합과 탐색의 시작점입니다.
BackTracking(0)을 호출하여 모든 경우의 수를 탐색하고, 정답을 출력합니다.
answer가 여전히 초기값인 987654321이면 경로가 없다는 뜻이므로 -1을 출력하고, 그렇지 않으면 최단 경로 길이를 출력합니다.

8. main()

프로그램의 시작점입니다.
Input()으로 데이터를 입력받고,
Game_Start()로 전체 조합을 탐색합니다.

전체 흐름 요약

미로 데이터 입력 → 5개의 5x5 층
각 층 회전 상태 저장 (총 4가지씩)
5개 층의 순서를 중복 없이 선택
각 층마다 4가지 회전 중 하나 선택
선택된 5개의 층을 3차원 미로로 구성
(0,0,0) → (4,4,4)까지 BFS로 경로 탐색
그 중 최소 경로를 저장하고 출력

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>

using namespace std;

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

typedef struct Node {
	int sero;
	int garo;
	int height;
	int count;
} Node;

typedef struct Idx {
	int sero;
	int garo;
	int height;
} Idx;

map<int, vector<vector<vector<int>>>> myMap;
vector<vector<vector<int>>> resultMap(5, vector<vector<int>>(5, vector<int>(5)));
bool used[5] = { false };
int perm[5]; 
int answer = 987654321;


vector<vector<int>> Rotate(vector<vector<int>> arr) {
	vector<vector<int>> copyArr(5, vector<int>(5));
	for (int i = 0; i < 5; i++) {
		for (int k = 0; k < 5; k++) {
			copyArr[k][4 - i] = arr[i][k];
		}
	}
	return copyArr;
}

void RotateAndInputMap(vector<vector<int>>& arr, int mapCount) {
	myMap[mapCount].push_back(arr);
	vector<vector<int>> rotatedArr = arr;
	for (int i = 0; i < 3; i++) {
		rotatedArr = Rotate(rotatedArr);
		myMap[mapCount].push_back(rotatedArr);
	}
}

void Input() {
	for (int i = 0; i < 5; i++) {
		vector<vector<int>> arr(5, vector<int>(5));
		for (int j = 0; j < 5; j++) {
			for (int k = 0; k < 5; k++) {
				cin >> arr[j][k];
			}
		}
		RotateAndInputMap(arr, i);
	}
}

bool isInside(int sero, int garo, int height) {
	return (sero >= 0 && sero < 5 && garo >= 0 && garo < 5 && height >= 0 && height < 5);
}


int BFS(Idx idxS, Idx idxE) {
	if (resultMap[idxS.height][idxS.sero][idxS.garo] == 0 ||
		resultMap[idxE.height][idxE.sero][idxE.garo] == 0) return -1;

	queue<Node> myQueue;
	vector<vector<vector<bool>>> visited(5, vector<vector<bool>>(5, vector<bool>(5, false)));
	myQueue.push({ idxS.sero, idxS.garo, idxS.height, 0 });
	visited[idxS.height][idxS.sero][idxS.garo] = true;

	while (!myQueue.empty()) {
		Node now = myQueue.front(); myQueue.pop();
		if (now.sero == idxE.sero && now.garo == idxE.garo && now.height == idxE.height) {
			return now.count;
		}

		for (int i = 0; i < 6; i++) {
			int nextSero = now.sero + dy[i];
			int nextGaro = now.garo + dx[i];
			int nextHeight = now.height + dz[i];
			if (!isInside(nextSero, nextGaro, nextHeight)) continue;
			if (resultMap[nextHeight][nextSero][nextGaro] == 0) continue;
			if (visited[nextHeight][nextSero][nextGaro]) continue;

			visited[nextHeight][nextSero][nextGaro] = true;
			myQueue.push({ nextSero, nextGaro, nextHeight, now.count + 1 });
		}
	}
	return -1;
}

void BackTracking(int depth) {
	if (depth == 5) {
		if (resultMap[0][0][0] == 0 || resultMap[4][4][4] == 0) return;
		int dist = BFS({ 0,0,0 }, { 4,4,4 });
		if (dist != -1) answer = min(answer, dist);
		return;
	}

	for (int i = 0; i < 5; i++) {
		if (used[i])continue;
		used[i] = true;
		for (int k = 0; k < 4; k++) {
			resultMap[depth] = myMap[i][k];
			BackTracking(depth + 1);
		}

		used[i] = false;
	}
}

void Game_Start() {
	BackTracking(0);
	cout << (answer == 987654321 ? -1 : answer);
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	Input();
	Game_Start();
}