백준16985 Maaaaaaaaaze

작성일 | In

문제 링크

  • http://icpc.me/16985

문제 출처

  • 2019 3/1 코딩테스트 특강 ( /Ba+rking/님 )

사용 알고리즘

  • BFS
  • Brute Force

풀이

3/1에 서울대학교에서 진행된 코딩테스트 특강 모의고사 문제입니다.

문제는 크게 3가지의 부분 문제로 분할됩니다.

  1. 판 회전 (rotating)
  2. 판 쌓기 (stacking)
  3. 길 찾기 (bfs)

한 가지 당연한듯 당연하지 않은듯한 사실 하나를 알면 문제를 푸는데 더 수월해집니다.
Lemma 1. 입구와 출구는 (0, 0, 0), (4, 4, 4)로 고정해도 무방하다.
proof ) 입구와 출구가 (0, 0, 0)과 (4, 4, 4)가 아닌 다른 곳이라고 가정을 하자. 큐브 전체를 적절히 돌리면 (0, 0, 0), (4, 4, 4)로 바꿀 수 있다.

이제, 한 단계씩 문제를 풀어봅시다.

1. 판 회전 (rotating)

00 01 02 03 04
10 11 12 13 14
20 21 22 23 24
30 31 32 33 34
40 41 42 43 44
 를
* 40 30 20 10 00
41 31 21 11 01
42 32 22 12 02
43 33 23 13 03
44 34 24 14 04
* 로 변환하는 과정을 생각해봅시다. 이는 (i, j)가 (j, 5-1-i)로 바뀐다는 사실을 쉽게 알 수 있습니다.
0 ≤ rot ≤ 3인 자연수 rot에 대해 입력받은 5개의 판을 모두 rot번 회전시킨 결과를 rotated[rot][i][j][k]에 저장해줍시다. 상세한 구현은 아래 코드에서 rotating함수 부분을 참고해주시기 바랍니다.

2. 판 쌓기 (stacking)

이 부분 문제에서는 permutation과 bitmask기법을 사용하여 쉽게 해결할 수 있습니다.
stackingOrder[] = {0, 1, 2, 3, 4} 배열에 대한 permutation을 모두 구해서 해당 순서대로 판을 쌓아주면 되기는 합니다만, 회전 처리가 남아있습니다.

5개의 판은 각각 0~3번 회전할 수 있고, 이진수로 나타내면 {00, 01, 10, 11}입니다. 총 10개의 비트를 만든 뒤, 2개씩 쪼개서 판의 회전 횟수로 나타낼 수 있습니다.
ㅇ 예를 들어 00 00 00 00 00은 5개의 판 모두 0번 회전을 한 것이고,
10 00 00 00 00은 첫 번째 판은 2번, 나머지는 0번을 회전한 것을 의미합니다.
0부터 (210-1)까지 순회하면 판이 회전하는 모든 경우를 탐색할 수 있습니다. 상세한 구현은 아래 코드에서 stacking함수 부분을 참고해주시기 바랍니다.

3. 길 찾기 (bfs)

이 부분은 전형적인 bfs구현입니다.

1
2
3
4
5
6
7
8
9
struct Node{
	int x, y, z;
	Node() : x(0), y(0), z(0) {}
	Node(int a, int b, int c) : x(a), y(b), z(c) {}
};

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

를 적절히 활용하면 bfs를 쉽게 구현할 수 있습니다.

추천 문제

KOI2013 지역 본선 초등부 3번 토마토 (링크)
KOI2000 초등부 3번 치즈 (링크)

두 문제 maze문제보다 모두 쉽긴 합니다만, bfs를 연습하는데는 좋은 문제라고 생각합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
using namespace std;

struct Node{
	int x, y, z;
	Node() : x(0), y(0), z(0) {}
	Node(int a, int b, int c) : x(a), y(b), z(c) {}
};

int dx[] = {1, -1, 0, 0, 0, 0};
int dy[] = {0, 0, 1, -1, 0, 0};
int dz[] = {0, 0, 0, 0, 1, -1};
const int n = 5, inf = 1e9+7; //size, maximum

int input[n][n][n]; //input data
int rotated[4][n][n][n];
int mp[n][n][n]; //current map
int stackingOrder[n] = {0, 1, 2, 3, 4};

inline bool bound(int x, int y, int z){
	return 0 <= x && x < n
		&& 0 <= y && y < n
		&& 0 <= z && z < n;
}

int bfs(){
	queue<Node> q; q.push({0, 0, 0});
	int dist[n][n][n]; memset(dist, -1, sizeof(dist));

	if(mp[0][0][0] == 0 || mp[4][4][4] == 0) return inf;
	dist[0][0][0] = 0;

	while(!q.empty()){
		Node now = q.front();
		int x = now.x, y = now.y, z = now.z;
		q.pop();

		for(int i=0; i<6; i++){
			int nxtX = x + dx[i];
			int nxtY = y + dy[i];
			int nxtZ = z + dz[i];
			if(!bound(nxtX, nxtY, nxtZ)) continue;
			if(dist[nxtX][nxtY][nxtZ] != -1) continue;
			if(mp[nxtX][nxtY][nxtZ] == 0) continue;
			if(nxtX == n-1 && nxtY == n-1 && nxtZ == n-1) return dist[x][y][z] + 1;
			dist[nxtX][nxtY][nxtZ] = dist[x][y][z] + 1;
			q.push({nxtX, nxtY, nxtZ});
		}
	}
	return inf;
}

void rotating(){
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			for(int k=0; k<n; k++)
				rotated[0][i][j][k] = input[i][j][k];

	for(int rot=1; rot<4; rot++){
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				for(int k=0; k<n; k++){
					rotated[rot][i][j][k] = rotated[rot-1][i][k][n-1-j];
				}
			}
		}
	}
}

void stacking(int bit){
	for(int i=0; i<n; i++){
		int idx = (bit&3); bit >>= 2;
		for(int j=0; j<n; j++){
			for(int k=0; k<n; k++){
				mp[i][j][k] = rotated[idx][stackingOrder[i]][j][k];
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			for(int k=0; k<n; k++)
				cin >> input[i][j][k];

	rotating();

	int ans = inf;

	do{
		for(int bit=0; bit<(1<<10); bit++){
			stacking(bit);
			ans = min(ans, bfs());
		}
	}while(next_permutation(stackingOrder, stackingOrder+n));

	if(ans > 1e9) ans = -1;
	cout << ans;
}