https://www.acmicpc.net/problem/16985
16985번: Maaaaaaaaaze
첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을
www.acmicpc.net
오랜만에 포스팅입니다. (너무 게을러서..)
bfs에 브루트포스까지 섞여있는 풀이가 복잡한 문제입니다.
5x5 크기의 2차원 배열이 5개 있으니 3차원 배열이 됩니다.
(0, 0, 0)에서 출발하여 (4, 4, 4)에 도착하는 최소 이동 횟수를 요구합니다.
여기까지만 보면, 단순 bfs로도 해결이 가능합니다.
하지만 5x5 크기의 판들의 순서도 변경이 가능하고, 판을 회전할 수도 있습니다.
브루트포스를 이 제약조건 두 개에 각각 적용해야 합니다.
저는 이 판들의 인덱스로 번호를 매겼고, dfs로 순회하면서 이동 횟수의 최솟값을 구하고, 회전 로직을 구현했습니다.
|
1
2
3
4
|
do {
copyArray();
dfs(0);
} while (next_permutation(order, order + MAX));
|
cs |
먼저, 순열을 이용하여 판들의 순서를 바꿔줍니다.
cpp은 next_permutation을 제공하여 편하게 구현할 수 있습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void dfs(int idx) {
if (idx == MAX) return;
for (int i = 0; i < 4; i++) {
int ret = bfs();
if (ret != -1) {
ans = min(ans, ret);
}
dfs(idx + 1);
rotate(idx);
}
}
|
cs |
처음 제출했을 때의 dfs 함수입니다.
모든 경우에서 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
|
int bfs() {
queue<pair<int, pair<int, int> > > q;
q.push({ 0,{0,0} });
memset(visit, false, sizeof(visit));
visit[0][0][0] = true;
for (int t = 0; !q.empty(); t++) {
int qsize = q.size();
while (qsize--) {
int x = q.front().first;
int y = q.front().second.first;
int z = q.front().second.second;
q.pop();
if (x == MAX - 1 && y == MAX - 1 && z == MAX - 1) {
return t;
}
for (int d = 0; d < 6; d++) {
int nx = x + direct[d][0];
int ny = y + direct[d][1];
int nz = z + direct[d][2];
if (nx < 0 || ny < 0 || nz < 0 || nx >= MAX || ny >= MAX || nz >= MAX) continue;
if (visit[nx][ny][nz] || !map[nx][ny][nz]) continue;
q.push({ nx,{ny,nz} });
visit[nx][ny][nz] = true;
}
}
}
return -1;
}
|
cs |
bfs로 이동 횟수를 구합니다.
중간에 도착 지점을 만났다면 t를 리턴, 아니면 -1을 리턴합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void rotate(int idx) {
int tmp[MAX][MAX][MAX] = { 0, };
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
tmp[idx][i][j] = map[idx][j][MAX - 1 - i];
}
}
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
map[idx][i][j] = tmp[idx][i][j];
}
}
}
|
cs |
현재 단계에서 이동횟수를 모두 구했다면 배열을 회전합니다.
회전은 90도, -90도 중에 아무렇게나 해주시면 됩니다. 한 방향으로 회전하는 것이 중요합니다.
이렇게 하시면 AC는 받을 수 있습니다.
하지만 다른 분들의 실행 시간을 보니 제 코드가 비효율적으로 동작한다는 것을 깨달았고, 가지치기를 진행하였습니다.
위의 코드들은 가지치기 이전 단계의 코드이며, 변화가 있는 로직은 rotate와 dfs입니다.
생각을 해보니, 문제에 답이 있었다는 것을 깨달았습니다.
- 참가자가 들어갈 수 없는 칸이 존재한다.
- 그 칸이 시작/도착 지점이라면 bfs 탐색할 필요가 없다.
- 배열은 회전하므로 시작/도착 지점이 갈 수 없는 칸일 가능성이 있다.
- 배열 크기는 5 x 5 x 5로 고정되어 있다.
- 탈출이 가능한 배열에서 나올 수 있는 최소 이동 횟수는 12다.
- 회전을 해도 이전과 같은 모양이 나올 수 있다.
- 이미 구한 것으로 간주하고, 다음 단계를 진행할 필요가 없다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
bool rotate(int idx) {
int tmp[MAX][MAX][MAX] = { 0, };
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
tmp[idx][i][j] = map[idx][j][MAX - 1 - i];
}
}
int cnt = 0;
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
if (map[idx][i][j] == tmp[idx][i][j]) cnt++;
map[idx][i][j] = tmp[idx][i][j];
}
}
if (cnt == MAX * MAX) return false;
else return true;
}
|
cs |
우선 rotate입니다.
자료형은 bool로 변경되었고, 회전한 배열이 이전 배열과 같은지 확인하는 로직만 추가되었습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
void dfs(int idx) {
if (idx == MAX) {
if (!map[MAX - 1][MAX - 1][MAX - 1]) {
return;
}
int ret = bfs();
if (ret != -1) {
ans = min(ans, ret);
}
return;
}
for (int i = 0; i < 4; i++) {
if (map[0][0][0]) {
dfs(idx + 1);
if (ans == MIN_ANS) return;
}
if (!rotate(idx)) return;
}
}
|
cs |
dfs 함수에 많은 변화가 있었습니다.
bfs 함수 호출은 모든 회전이 한 번씩 끝났을 때 진행하는 것으로 변경하였고, 출발/도착 지점에 대한것과 최솟값, rotate에 대한 가지치기가 모두 포함되어 있습니다.
이제 제출을 해보니 시간이 많이 줄어든 것을 확인할 수 있습니다.
최종 코드는 아래입니다.
|
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#define MAX 5
#define MIN_ANS 12
using namespace std;
int list[MAX][MAX][MAX], map[MAX][MAX][MAX];
int order[MAX], ans;
int direct[6][3] = { {0,0,1}, {0,0,-1}, {0,1,0}, {0,-1,0}, {1,0,0}, {-1,0,0} };
bool visit[MAX][MAX][MAX];
int bfs() {
queue<pair<int, pair<int, int> > > q;
q.push({ 0,{0,0} });
memset(visit, false, sizeof(visit));
visit[0][0][0] = true;
for (int t = 0; !q.empty(); t++) {
if (ans <= t) return t;
int qsize = q.size();
while (qsize--) {
int x = q.front().first;
int y = q.front().second.first;
int z = q.front().second.second;
q.pop();
if (x == MAX - 1 && y == MAX - 1 && z == MAX - 1) {
return t;
}
for (int d = 0; d < 6; d++) {
int nx = x + direct[d][0];
int ny = y + direct[d][1];
int nz = z + direct[d][2];
if (nx < 0 || ny < 0 || nz < 0 || nx >= MAX || ny >= MAX || nz >= MAX) continue;
if (visit[nx][ny][nz] || !map[nx][ny][nz]) continue;
q.push({ nx,{ny,nz} });
visit[nx][ny][nz] = true;
}
}
}
return -1;
}
bool rotate(int idx) {
int tmp[MAX][MAX][MAX] = { 0, };
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
tmp[idx][i][j] = map[idx][j][MAX - 1 - i];
}
}
int cnt = 0;
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
if (map[idx][i][j] == tmp[idx][i][j]) cnt++;
map[idx][i][j] = tmp[idx][i][j];
}
}
if (cnt == MAX * MAX) return false;
else return true;
}
void dfs(int idx) {
if (idx == MAX) {
if (!map[MAX - 1][MAX - 1][MAX - 1]) {
return;
}
int ret = bfs();
if (ret != -1) {
ans = min(ans, ret);
}
return;
}
for (int i = 0; i < 4; i++) {
if (map[0][0][0]) {
dfs(idx + 1);
if (ans == MIN_ANS) return;
}
if (!rotate(idx)) return;
}
}
void copyArray() {
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
for (int k = 0; k < MAX; k++) {
map[order[i]][j][k] = list[i][j][k];
}
}
}
}
void func() {
ans = 1e9;
do {
copyArray();
dfs(0);
} while (next_permutation(order, order + MAX));
if (ans == 1e9) ans = -1;
cout << ans << '\n';
}
void input() {
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
for (int k = 0; k < MAX; k++) {
cin >> list[i][j][k];
}
}
order[i] = i;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 14466 소가 길을 건너간 이유 6 (1) | 2022.10.13 |
|---|---|
| boj 18112 이진수 게임 (2) | 2022.09.16 |
| boj 16946 벽 부수고 이동하기 4 (0) | 2022.05.22 |
| boj 5547 일루미네이션 (0) | 2022.05.15 |
| boj 16932 모양 만들기 (0) | 2022.05.14 |
