문제 URL : https://www.acmicpc.net/problem/16985
16985번: Maaaaaaaaaze
첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을
www.acmicpc.net
문제접근법 : 문제 잘읽어야합니다.
제출할때는 한번에 맞았지만 제출전 테스트케이스안에서 여러번 다르게 나와서
문제를 몇번이고 다시 읽었습니다.
핵심은 시뮬레이션 + bfs인데
핵심 1 : 1층부터 5층까지 내마음대로 삽입해서 새로운 큐브를 만들어야한다
핵심 2 : 회전해서 하나의 새로운 큐브를 만든다.
핵심 3 : 출발지점이 1이 아니라면 bfs를 돌지않는다.
이렇게해서 0,0,0 에서 출발해서 4,4,4까지 최단거리를 구하는 문제입니다.
첫째 :우선 1층부터 5층까지 내마음대로 새로운 큐브를 만들기위해서 5! 이라는 순열을 이용해서 만들기때문에 120가지 큐브가 만들어집니다.
아래처럼 사진처럼
둘째 회전방향은 신경쓰지 않았습니다. 왼쪽으로 90도 회전을 해봤자 오른쪽으로 270도 회전해도 똑같으니 그냥 시계방향으로 90도 회전하는 표현만 했고 그것을 최대 3번까지만 하면되니까
회전을 해야하기때문에 90, 180, 270, 360 ,360도는 회전하나마나 이니 회전 시키지 않았습니다.
총 4가지 나오기때문에 1층부터 5층까지 회전의 경우수는 4^5=1024가지가 나옵니다.
이렇게 삽입해서 나오는 경우의수 120, 회전해서 나오는경우의수 1024가지 이것을 곱하면
120*1024 = 122840 이나오기때문에 bfs돌릴만합니다.
큐브로 최단거리 구하는 경우라 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
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
|
//By 콩순이냉장고
#include<iostream>
#include<string>
#include<algorithm>
#include <vector>
#include <queue>
using namespace std;
int n = 5;
int cube[5][5][5];
int dy[6] = { -1, 0, 1, 0, 0, 0 };
int dx[6] = { 0, 1, 0, -1, 0, 0 };
int dz[6] = { 0, 0, 0, 0, 1, -1 };//3차원 움직이는 방향
struct Point{
int z, y, x, cnt;
Point(int z, int y, int x, int cnt) :z(z), y(y), x(x), cnt(cnt){}
};
void Copy(int a[5][5], int b[5][5]){//2차원 copy
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
a[i][j] = b[i][j];
}
void CubeCopy(int a[5][5][5], int b[5][5][5])//3차원 copy
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++){
a[i][j][k] = b[i][j][k];
}
}
}
}
void rotate(int idx){//오른쪽으로만 90도 회전하는 함수
int temp[5][5];
Copy(temp, cube[idx]);
int j2 = n - 1;
for (int i = 0; i < n; i++)
{
int i2 = 0;
for (int j = 0; j < n; j++){
cube[idx][i2++][j2] = temp[i][j];
}
j2--;
}
}
void input()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++){
cin >> cube[i][j][k];
}
}
}
}
bool isrange(int z, int y, int x){
if (0 <= z&&z < n && 0 <= y&&y < n && 0 <= x&&x < n)
return true;
return false;
}
int bfs()
{
char visit[5][5][5] = { 0 };
queue<Point> q;
q.push({ 0, 0, 0, 0 });
visit[0][0][0] = 1;
while (!q.empty()){
int y = q.front().y;
int x = q.front().x;
int z = q.front().z;
int cnt = q.front().cnt;
q.pop();
if (z == n - 1 && y == n - 1 && x == n - 1)//도착지점
return cnt;
for (int i = 0; i < 6; i++)
{
int nz = z + dz[i];
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(nz, ny, nx) && visit[nz][ny][nx] == 0 && cube[nz][ny][nx])
{
q.push({ nz, ny, nx, cnt + 1 });
visit[nz][ny][nx] = 1;
}
}
}
return 1e+9;//도착지점에 갈수없음
}
void solve(){
int res = 1e+9;
int originalcube[5][5][5];//원래 입력받았던 qube 저장
CubeCopy(originalcube, cube);
vector<int> v;
for (int i = 0; i < n; i++)//판을 내멋대로 바꿀수있음 5!의개수를 구해야함
v.push_back(i);
do{
CubeCopy(cube, originalcube);//처음입력받았던큐브를 늘 갱신
for (int i = 0; i < v.size(); i++)// 큐브의 판을 내가 원하는대로 삽입 이게 핵심
Copy(cube[i], originalcube[v[i]]);
int tcube[5][5][5];//회전하는 큐브만들기
CubeCopy(tcube, cube);//판을 만들었던 큐브를 만든것을 tcube에 넣음
for (int i = 0; i < 1024; i++)//회전하는 경우의수 만들기
{
int t = i;
vector<int> v;
for (int j = 0; j < 5; j++) // 0 0 0 0 0 ~ 3 3 3 3 3 까지 만들어줌
{
v.push_back(t % 4);//회전수
t /= 4;
}
for (int j = 0; j < 5; j++)
{
int r = v[j];//몇번회전해야하는지
for (int k = 0; k < r; k++){//회전수만큼 회전해줌
rotate(j);//j번째판 회전 이게중요
}
}
int c = 1e+9;
if (cube[0][0][0])//시작점이 1만 출발해야함 핵심임
c = bfs();
res = min(res, c);
CubeCopy(cube, tcube);//회전한거 다시 원상복구 시켜야함
}
} while (next_permutation(v.begin(), v.end()));
printf("%d\n", (res == 1e+9 ? -1 : res));
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
solve();
vector<int> v;
}
|
cs |
궁금한점 혹은 모르는것,혹은 제가 틀린것이 있다면 언제든지 댓글을 이용해주시길 부탁드립니다. ㅎㅎ
'백준' 카테고리의 다른 글
| 백준 10473 인간 대포 (0) | 2020.08.25 |
|---|---|
| 백준 1781 컵라면 (0) | 2020.08.25 |
| 백준 16946 벽 부수고 이동하기 4 (0) | 2020.08.24 |
| 백준 1202 보석 도둑 (0) | 2020.08.24 |
| 백준 17299 오등큰수 (0) | 2020.08.13 |
