반응형
https://www.acmicpc.net/problem/6593
6593번: 상범 빌딩
당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어
www.acmicpc.net
이 문제는 일반 탐색문제와 거의 흡사하지만 고려해주어야 할게 하나 더 추가된 형식이다. 바로 층 수가 있다는 것이다. 보통 탐색 문제의 경우 상하좌우만 움직여 좌표를 2개만 설정해주지만 이 문제 같은 경우 층 수도 고려를 해주어야 하기 때문에 층을 고려하는 좌표를 하나 추가해주어 풀어주면 간단히 해결된다. 나는 bfs를 이용하여 큐에 x,y,z,count를 튜플로 만들어 넣어주어 문제를 해결하였다. bfs 구현 같은 경우 dx,dy,dz를 이용하여 6개의 이동을 표현해 주었고 만약 탈출을 하지 못한경우 found 변수로 false를 주어 결과 벡터에 -1로 저장후 if문을 통해 trapped을 출력하게 만들었다. 탈출을 했을 경우 found를 true로 만들어주고 count값을 결과 벡터에 넣어주었다.
전체코드
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
|
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
#include <string.h>
using namespace std;
int l, r, c;
char building[31][31][31];
bool visit[31][31][31];
int dx[] = {1,-1,0,0,0,0}; // 동서남북상하
int dy[] = {0,0,-1,1,0,0};
int dz[] = {0,0,0,0,1,-1};
vector<int> result;
bool found = false;
void bfs(int x1, int y1,int z1, int c1){
queue<tuple<int, int, int, int>> q;
q.push(make_tuple(x1, y1, z1, c1));
visit[z1][y1][x1] = true;
while(!q.empty()){
int x = get<0>(q.front());
int y = get<1>(q.front());
int z = get<2>(q.front());
int cnt = get<3>(q.front());
if(building[z][y][x]=='E'){
found = true;
result.push_back(cnt);
break; // 탈출 했을 경우
}
q.pop();
for (int i = 0; i < 6;i++){
int n_x = x + dx[i];
int n_y = y + dy[i];
int n_z = z + dz[i];
if (n_x >= 0 && n_y >= 0 && n_z >= 0 && n_x < c && n_y < r && n_z < l){
if(!visit[n_z][n_y][n_x] && building[n_z][n_y][n_x]!='#'){
q.push(make_tuple(n_x, n_y, n_z,cnt+1));
visit[n_z][n_y][n_x] = true;
}
}
}
}
}
int main(){
while(1){
cin >> l >> r >> c;
if (l == 0 && r == 0 && c == 0){
break; // 000이 들어오면 종료
}
int start_x, start_y, start_z;
memset(visit, false, sizeof(visit));
found = false;
for (int i = 0; i < l;i++){
for (int j = 0; j < r; j++){
for (int k = 0; k < c; k++){
cin >> building[i][j][k];
if( building[i][j][k] == 'S'){
start_x = k;
start_y = j;
start_z = i; //시작 좌표 저장
}
}
}
}
bfs(start_x, start_y, start_z, 0);
if(!found){ // 탈출을 못했을 경우
result.push_back(-1);
}
}
for (int i = 0; i < result.size();i++){
if(result[i] == -1){
cout << "Trapped!" << '\n';
}
else{
cout << "Escaped in " << result[i] << " minute(s)." << '\n';
}
}
return 0;
}
|
cs |
사용 문법 : bfs, tuple
yea!
반응형
'알고리즘 > 백준' 카테고리의 다른 글
백준 2636 치즈 c++ [컴공과고씨] (0) | 2022.03.21 |
---|---|
백준 1697 숨바꼭질 c++ [컴공과고씨] (0) | 2022.03.21 |
백준 2583 영역 구하기 c++ [컴공과고씨] (0) | 2022.03.19 |
백준 2206 벽 부수고 이동하기 c++ [컴공과고씨] (0) | 2022.03.19 |
백준 1260 DFS와 BFS C++ [컴공과고씨] (0) | 2022.03.19 |