[ 백준 / 16985 ] Maaaaaaaaaze (C++)

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

 

난이도 : 골드 2 
알고리즘 유형 : 완전탐색, BFS 
풀이 시간 : 1시간 28분 

문제 풀이 

문제가 매우 길기 때문에 간략히 요약해보자

• 5 x 5 x 5 사이즈의 미로가 존재한다.
• 주어진 판들은 시계 or 반시계 방향으로 회전이 가능하다.
• 참가자는 판 5개를 무작위로 쌓는다.
• 입구에서 입구와 면을 공유하지 않는 꼭짓점인 출구까지 가는 데 걸리는 이동거리의 최솟값을 구하자.

이 문제를 처음 접할 때는 매우 고려해야 할 사항이 많지만, 일단 천천히 생각해보자.

우리가 고려해야 할 부분은 다음과 같다.

 

1. 시계 방향 혹은 반시계 방향으로 회전이 가능하다.

; 위 이슈의 경우, 어떤 방향으로 회전하든지 한 방향만 택해서 회전하면 된다. 어차피 어느 쪽을 우선으로 돌리든 같은 결과를 얻기 때문이다.

2. 각 판을 선택해서 사용자 마음대로 쌓아올린다.

; 이 이슈의 경우, 순열을 사용해야한다. 모든 경우의 수에 대해서 수행해보는 수밖에 없다.

 

위 두 가지 경우에 대한 총 가지수를 계산해보면, 각 층마다 회전을 해야 하기 때문에 $4^5$번 진행하게 될 것이고, 순열을 계산해야 하기 때문에 $5! = 120$ 번의 연산이 수행되어 총 $4^5 * 120 = 122880$번 연산이 수행된다.

 

이 모든 경우를 끝내 큐브를 완성시켰으면 BFS를 통해 출구까지의 최단경로를 계산해야 한다.

문제에서는 특정 입구와 출구가 정해져있지 않았지만, 결국 모든 큐브의 경우의 수를 계산한 뒤 BFS를 수행할 것이기 때문에, `(0, 0, 0)`을 입구로, `(4, 4, 4)`를 출구로 생각하여 문제를 풀어나가면 된다.

 

시간복잡도를 구해보면, 배열을 돌리는데 필요한 $O(4^n)$, 순열을 생성하는데 필요한 $O(n!), 그리고 BFS를 수행하는데 필요한 $O(n^3)$으로 총 $O(4^n * n! * n^3)$만큼 소요된다.

 

추가) 본인은 해당 문제를 C++ STL인 vector를 사용해 풀었는데, 실행 시간이 매우 오래 걸렸다. 다시 생각해보니 vector는 메모리 주소 공간을 동적 할당하여 사용하기 때문에, 정적으로 할당한 배열보다 더 큰 시간이 소요될 것이라고 생각하였다. 배열을 복사하거나 재사용 할 때는 무조건 C-style의 배열을 사용하자 !

 

코드

/*
5 x 5 x 5
주어진 판들은 시계 or 반시계 방향으로 회전 가능함
회전을 완료한 후, 참가자는 판 5개를 쌓는다. -> 순서는 자유롭게 정할 수 있음
참가자는 칸에서 변으로 인접한 칸이 들어갈 수 있는 칸인 경우, 그 칸으로 이동 가능함
본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 우승한다. 
가장 적은 이동 횟수를 구해보자

풀이 : 시뮬레이션, BFS
rotate, 조합 필요한데 시계나 반시계나 두 방향 중 한 방향으로만 돌리면 된다.(결국 같음)
각 판 선택해서 회전하고 & 조합 만들고 & bfs 진행
-> 재귀 + 조합 재귀 + bfs
입구와 출구가 정해져있지 않으므로 총 4번 진행해봐야함
4^5 * 2^5 * 4 * 5 * 5 * 5
-----------------------------------------------------------------
배열 복사 문제의 경우 vector보다 그냥 array 쓰는게 효율이 더 좋다.
== vector는 동적 할당이다.
*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#define INF 5 * 5 * 5 * 5

using namespace std;

struct Node {
	int h, r, c;
};

int n = 5, ans = INF;
int visited[5][5][5];
int selected[5];
vector<vector<vector<int>>> grid;
Node entrance = {4, 0, 0};

int dr[6] = { 0, 1, 0, -1, 0, 0 };
int dc[6] = { 1, 0, -1, 0, 0, 0 };
int dh[6] = { 0, 0, 0, 0, -1, 1 };

void init() {
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

	int tmp;
	for (int i = 0; i < n; i++) {
		vector<vector<int>> tmp_grid(n);
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				cin >> tmp;
				tmp_grid[j].push_back(tmp);
			}
		}
		grid.push_back(tmp_grid);
		tmp_grid.clear();
	}
}


bool canMove(Node u) {
	return 0 <= u.h && u.h < n && 0 <= u.r && u.r < n && 0 <= u.c && u.c < n;
}


void bfs(Node entrance, vector<vector<vector<int>>> grid) {
	Node exit = { abs(entrance.h - 4), abs(entrance.r - 4), abs(entrance.c - 4) };
	// 입구 혹은 출구가 막혔는지 확인
	if (!grid[entrance.h][entrance.r][entrance.c] || !grid[exit.h][exit.r][exit.c])
		return;

	memset(visited, -1, sizeof(visited));
	queue<Node> queue;
	queue.push(entrance);
	visited[entrance.h][entrance.r][entrance.c] = 0;

	while (!queue.empty()) {
		Node u = queue.front();
		queue.pop();

		if (ans <= visited[u.h][u.r][u.c])
			continue;

		for (int d = 0; d < 6; d++) {
			Node v = { u.h + dh[d], u.r + dr[d], u.c + dc[d] };
			if (canMove(v) && visited[v.h][v.r][v.c] == -1 && grid[v.h][v.r][v.c]) {
				// 도착지인 경우 종료
				if (v.h == exit.h && v.r == exit.r && v.c == exit.c) {
					ans = min(ans, visited[u.h][u.r][u.c] + 1);
					return;
				}
				queue.push(v);
				visited[v.h][v.r][v.c] = visited[u.h][u.r][u.c] + 1;
			}
		}
	}
}


void build_cube(int depth, vector<vector<vector<int>>> cube, vector<vector<vector<int>>> grid) {
	if (depth == 5) {
		// bfs 진행
		// (0, 0, 0 / 4, 4, 4), (0, 0, 4 / 4, 4, 0), (0, 4, 0 / 4, 0, 4), (0, 4, 4 / 4, 0, 0)
		bfs(entrance, cube);
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!selected[i]) {
			selected[i] = 1;
			cube.push_back(grid[i]);
			build_cube(depth + 1, cube, grid);
			cube.pop_back();
			selected[i] = 0;
		}
	}
}


vector<vector<int>> rotate(vector<vector<int>> grid) {
	vector<vector<int>> new_grid(n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			new_grid[i].push_back(0);
	}
	// rotate 시작
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			new_grid[j][n - i - 1] = grid[i][j];
		}
	}

	return new_grid;
}


void rotate_grid(int depth, vector<vector<vector<int>>> grid) {
	if (depth == 5) {
		// 모든 애들 다 돌렸으면 층 새로 쌓기
		vector<vector<vector<int>>> tmp_cube;
		build_cube(0, tmp_cube, grid);
		return;
	}
		
	for (int i = 0; i < 4; i++) {
		grid[depth] = rotate(grid[depth]);
		rotate_grid(depth + 1, grid);

	}
}



int main() {
	init();

	// rotate 먼저 진행
	rotate_grid(0, grid);

	if (ans == INF)
		ans = -1;
	cout << ans << '\n';

	return 0;
}

배운 점 

구현 문제 혹은 배열 복사의 경우에는 정적 배열을 할당하여 값을 변경해주는 방식이 가장 효율적이고 편리하다.

그리드와 visited와 같은 정적 배열의 경우, 전역 변수로 세팅해두고 값을 초기화해가며 사용하자. 이게 젤 good !

C++로 구현 문제는 오랜만에 풀어봤지만, 해당 방법을 숙지하자