기술 블로그

16985번 Maaaaaaaaaze 본문

알고리즘 문제/BOJ

16985번 Maaaaaaaaaze

parkit 2019. 3. 25. 14:28
728x90
반응형

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



서울대학교 3/1 알고리즘 특강 문제 → https://www.acmicpc.net/contest/view/395


서울대학교 3/2 알고리즘 특강 문제 → https://www.acmicpc.net/contest/view/396




이 문제는 보자마자


Backtracking(next_permutation, 5중 for문), Bruteforce, BFS, Simulation의 짬뽕 문제임을 느꼈다.




우선, 총 5개의 층이 있고, 각각 4가지의 모습(회전)이 가능하므로, 4^5가 가능하다.(4*5 아님.)


그리고 총 5개의 층들을 배치시키는 경우의 수 5!


그리하여, BFS를 돌리면 총 6개의 방향으로 5*5*5의 칸들을 고려하면,


 5*5*5*6*4^5*5! 쯤 된다.



참고로, 

입구는 (0, 0, 0), 출구는 (4, 4, 4)로 고정시켜도 풀린다.



회전은 아래처럼 써가면서 추측하였다.


[0][0] → [0][4]

[0][1] → [1][4]

[0][2] → [2][4]

[0][3] → [3][4]

[0][4] → [4][4]

[1][0] → [0][3]

[1][1] → [1][3]

.

.

.

[i][j] → [j][4-i]


그런데 계속 답이 안 나오길래 생각해보았다.


내가 멍청하게 rotate() 함수를 아래처럼 구현했었다.


1
2
3
4
5
6
7
8
9
10
void rotate(int h)
{
    for (int i = 0; i < 5; i++) 
    {
        for (int j = 0; j < 5; j++) 
        {
            temp[j][4 - i][h] = temp[i][j][h];
        }
    }
}
cs


하도 답이 안 나오길래, 실행하면서 Test 해보니 


rotate 함수 내에서 temp를 저장할 임시의 변수가 필요했었다. 


이렇게 구현하고 제출하니 맞았다.




아래에 총 2개의 코드가 있는데

첫 번째 코드는 backtracking 함수를 구현한 것 이고

두 번째 코드는 코드 길이를 줄이기 위해 C++ STL next_permutation을 사용하였다.





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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
// https://www.acmicpc.net/problem/16985
// 90도 시계 방향 회전 [i][j] → [j][4-i]
 
#define MAX 987654321
 
typedef struct yxz
{
    int y;
    int x;
    int z;
}yxz;
 
int dy[6] = { 0, 0, 0, 1, 0, -1 };
int dx[6] = { 0, 0, 1, 0, -1, 0 };
int dz[6] = { 1, -1, 0, 0, 0, 0 };
 
int Map[5][5][5] = { 0, }; // 입력할 미로
 
int temp[5][5][5] = { 0, }; // 경우의 수(판을 쌓는 일), 총 5! = 120
 
bool used[5] = { false, };
 
bool stop = false;
 
int ans = 0;
 
vector<int> v = { 0, 1, 2, 3, 4 };
 
yxz input;
 
int BFS()
{
    queue<yxz> q;
 
    bool visit[5][5][5] = { false, };
 
    memset(visit, false, sizeof(visit));
 
    q.push({ 0, 0, 0 });
 
    visit[0][0][0] = true;
 
    int ret = 0;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int y = q.front().y;
            int x = q.front().x;
            int z = q.front().z;
 
            q.pop();
 
            if (y == 4 && x == 4 && z == 4) return ret;
        
            for (int i = 0; i < 6; i++)
            {
                int r = y + dy[i];
                int c = x + dx[i];
                int h = z + dz[i];
 
                if (r < 0 || r >= 5 || c < 0 || c >= 5 || h < 0 || h >= 5 || temp[r][c][h] == 0 || visit[r][c][h]) continue;
 
                input.y = r;
                input.x = c;
                input.z = h;
 
                q.push(input);
                visit[r][c][h] = true;
            }
        }
 
        ++ret;
    }
 
    return -1;
}
 
void rotate(int h)
{
    int arr[5][5][5] = { 0, };
    // 회전한 배열을 잠시 저장할 임시 변수
 
    for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) arr[j][4 - i][h] = temp[i][j][h];
 
    for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) temp[i][j][h] = arr[i][j][h]; 
    // 대입
}
 
void backtracking(vector<int> vc)
{
    if (vc.size() == 5)
    {
        for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) for (int k = 0; k < 5; k++) temp[i][j][k] = Map[i][j][vc.at(k)];
 
        for (int a = 0; a < 4 && !stop; a++)
        {
            rotate(0);
 
            for (int b = 0; b < 4 && !stop; b++)
            {
                rotate(1);
 
                for (int c = 0; c < 4 && !stop; c++)
                {
                    rotate(2);
 
                    for (int d = 0; d < 4 && !stop; d++)
                    {
                        rotate(3);
 
                        for (int e = 0; e < 4 && !stop; e++)
                        {
                            rotate(4);
 
                            if (temp[0][0][0] == 1 && temp[4][4][4] == 1)
                            {
                                int Get = BFS();
 
                                if (Get == -1) continue;
                                // -1이 return되었다는 것은 도달 불가능이므로 continue
 
                                ans = min(ans, Get);
 
                                if (ans == 12) stop = true;
                            }
                        }
                    }
                }
            }
        }
 
        return;
    }
 
    for (int i = 0; i < 5; i++)
    {
        if (!used[i])
        {
            vc.push_back(v.at(i));
            used[i] = true;
 
            backtracking(vc);
 
            vc.pop_back();
            used[i] = false;
        }
    }
}
 
int main(void)
{
    ans = MAX;
 
    for (int h = 0; h < 5; h++) for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) scanf("%d", &Map[i][j][h]);
 
    vector<int> vc;
 
    backtracking(vc);
 
    if(ans == MAX) printf("-1\n");
    else printf("%d\n", ans);
 
    return 0;
}
cs














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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
// https://www.acmicpc.net/problem/16985
// 90도 시계 방향 회전 [i][j] → [j][4-i]
 
#define MAX 987654321
 
typedef struct yxz
{
    int y;
    int x;
    int z;
}yxz;
 
int dy[6] = { 0, 0, 0, 1, 0, -1 };
int dx[6] = { 0, 0, 1, 0, -1, 0 };
int dz[6] = { 1, -1, 0, 0, 0, 0 };
 
int Map[5][5][5] = { 0, }; // 입력할 미로
 
int temp[5][5][5] = { 0, }; // 경우의 수(판을 쌓는 일), 총 5! = 120
 
vector<int> v = { 0, 1, 2, 3, 4 };
 
yxz input;
 
int BFS()
{
    queue<yxz> q;
 
    bool visit[5][5][5] = { false, };
 
    memset(visit, false, sizeof(visit));
 
    q.push({ 0, 0, 0 });
 
    visit[0][0][0] = true;
 
    int ret = 0;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int y = q.front().y;
            int x = q.front().x;
            int z = q.front().z;
 
            q.pop();
 
            if (y == 4 && x == 4 && z == 4) return ret;
        
            for (int i = 0; i < 6; i++)
            {
                int r = y + dy[i];
                int c = x + dx[i];
                int h = z + dz[i];
 
                if (r < 0 || r >= 5 || c < 0 || c >= 5 || h < 0 || h >= 5 || temp[r][c][h] == 0 || visit[r][c][h]) continue;
 
                input.y = r;
                input.x = c;
                input.z = h;
 
                q.push(input);
                visit[r][c][h] = true;
            }
        }
 
        ++ret;
    }
 
    return -1;
}
 
void rotate(int h)
{
    int arr[5][5][5] = { 0, };
    // 회전한 배열을 잠시 저장할 임시 변수
 
    for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) arr[j][4 - i][h] = temp[i][j][h];
 
    for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) temp[i][j][h] = arr[i][j][h]; 
    // 대입
}
 
int main(void)
{
    bool stop = false;
 
    int ans = MAX;
 
    for (int h = 0; h < 5; h++) for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) scanf("%d", &Map[i][j][h]);
 
    while (next_permutation(v.begin(), v.end())) // 5!
    {
        for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) for (int k = 0; k < 5; k++) temp[i][j][k] = Map[i][j][v.at(k)];
 
        for (int a = 0; a < 4 && !stop; a++)
        {
            rotate(0);
 
            for (int b = 0; b < 4 && !stop; b++)
            {
                rotate(1);
 
                for (int c = 0; c < 4 && !stop; c++)
                {
                    rotate(2);
 
                    for (int d = 0; d < 4 && !stop; d++)
                    {
                        rotate(3);
 
                        for (int e = 0; e < 4 && !stop; e++)
                        {
                            rotate(4);
 
                            if (temp[0][0][0] == 1 && temp[4][4][4] == 1)
                            {
                                int Get = BFS();
 
                                if (Get == -1) continue;
                                // -1이 return되었다는 것은 도달 불가능이므로 continue
 
                                ans = min(ans, Get);
 
                                if (ans == 12) stop = true;        
                            }
                        }
                    }
                }
            }
        }
 
        if (stop) break;
    }
 
    if(ans == MAX) printf("-1\n");
    else printf("%d\n", ans);
 
    return 0;
}
cs



























728x90
반응형
저작자표시

'알고리즘 문제 > BOJ' 카테고리의 다른 글

6087번 레이저 통신  (0) 2019.03.28
16932번 모양 만들기  (1) 2019.03.27
13414번 수강신청  (0) 2019.03.23
1181번 단어 정렬  (0) 2019.03.22
16931번 겉넓이 구하기  (0) 2019.03.21
'알고리즘 문제/BOJ' Related Articles more