반응형
문제 링크: https://www.acmicpc.net/problem/16985
16985번: Maaaaaaaaaze
첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을
www.acmicpc.net
<문제 풀이> 시뮬레이션, BFS, 조합, next_permutation
1. 각 판 회전시키기 구현
2. next_permutation을 이용해서 각 판 쌓기 구현
3. BFS로 시작점부터 도착점까지 최단거리 구하기
-> 이때 큐브의 입구는 정육면체에서 참가자가 임의로 선택한 꼭짓점에 위치한 칸이고 출구는 입구와 면을 공유하지 않는 꼭짓점에 위치한 칸이다.
-> 시작점을 0, 0, 0 / 도착점을 4, 4, 4로 고정해도 되는 이유는 시작점과 도착점을 고정시키고 판을 잘 회전시키고 잘 쌓으면 다른 꼭짓점에서 출발시킨 것과 동일하다.
4. 판을 회전시키는 모든 경우에 대해서 진행
<C++ 소스 코드>
|
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int maze[5][5][5]; //판을 쌓은 미로
int board[5][5][5]; //5개의 판
int dist[5][5][5];
const int dx[6] = {0, 0, 0, 0, 1, -1};
const int dy[6] = {0, 0, 1, -1, 0, 0};
const int dz[6] = {1, -1, 0, 0, 0, 0};
int res = 125;
vector<int> v{ 0, 1, 2, 3, 4 }; //쌓일 판의 순서
class pos {
public:
int z;
int x;
int y;
pos(int z, int x, int y) : z(z), x(x), y(y) {
}
};
void stackMaze() {
for (int z = 0; z < 5; z++) {
for (int x = 0; x < 5; x++) {
for (int y = 0; y < 5; y++) {
maze[z][x][y] = board[v[z]][x][y];
}
}
}
}
void init() {
for (int z = 0; z < 5; z++) {
for (int x = 0; x < 5; x++) {
for (int y = 0; y < 5; y++) {
dist[z][x][y] = 0;
}
}
}
}
void rotate(int z) {
int temp[5][5];
for (int x = 0; x < 5; x++) {
for (int y = 0; y < 5; y++) {
temp[x][y] = board[z][x][y];
}
}
for (int x = 0; x < 5; x++) {
for (int y = 0; y < 5; y++) {
board[z][y][4 - x] = temp[x][y];
}
}
}
int bfs() {
if (maze[0][0][0] == 0 || maze[4][4][4] == 0) return -1; //입구 혹은 출구가 막혀있을 경우
pos p(0, 0, 0);
queue<pos> Q;
Q.push(p);
dist[p.z][p.x][p.y] = 1;
while (!Q.empty()) {
auto cur = Q.front(); Q.pop();
for (int dir = 0; dir < 6; dir++) {
int nz = cur.z + dz[dir];
int nx = cur.x + dx[dir];
int ny = cur.y + dy[dir];
if (nz < 0 || nx < 0 || ny < 0 || nz >= 5 || nx >= 5 || ny >= 5)continue;
if (maze[nz][nx][ny] == 0 || dist[nz][nx][ny]) continue;
Q.push({ nz, nx,ny });
dist[nz][nx][ny] = dist[cur.z][cur.x][cur.y] + 1;
if (nz == 4 && nx == 4 && ny == 4) return dist[nz][nx][ny];
}
}
return -1;
}
void solve(int k) {
if (k == 5) return;
for (int i = 0; i < 4; i++) { //k번째 판을 4번까지 회전시켜본다
rotate(k);
do {
stackMaze();
int ret = bfs();
if (ret != -1) res = min(res, ret);
init();
} while (next_permutation(v.begin(), v.end())); //판을 쌓는 순열
for (int m = 0; m < 5; m++)v[m] = m;
solve(k + 1); // k+1번째 판을 4번까지 회전시켜본다.
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
for (int z = 0; z < 5; z++) {
for (int x = 0; x < 5; x++) {
for (int y = 0; y < 5; y++) {
cin >> board[z][x][y];
}
}
}
solve(0);
if (res == 125) cout << "-1";
else cout << res - 1;
return 0;
}
|
cs |
반응형
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [백준 3190번] 뱀 (0) | 2022.01.19 |
|---|---|
| [백준 2638번] 치즈 (0) | 2022.01.17 |
| [백준 14499번] 주사위 굴리기 (0) | 2022.01.15 |
| [백준 6443번] 애너그램 (0) | 2022.01.14 |
| [백준 11559번] Puyo Puyo (0) | 2022.01.13 |
