반응형
문제 링크: https://www.acmicpc.net/problem/6593
6593번: 상범 빌딩
당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어
www.acmicpc.net
<문제 풀이> BFS
BFS로 dx, dy 방향으로 최단거리를 구하는 문제에서 dz 방향이 추가된 문제입니다.
3차원 배열 입력과, dz방향 추가만 고려하면 구현하는 건 2차원과 동일합니다.
int dx[6] = { 0,0, 1, -1, 0, 0 }; //동 서 남 북 상 하
int dy[6] = { 1,-1, 0, 0, 0 , 0 };
int dz[6] = { 0, 0, 0, 0 , 1, -1 };
<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
|
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
int dx[6] = { 0,0, 1, -1, 0, 0 }; //동 서 남 북 상 하
int dy[6] = { 1,-1, 0, 0, 0 , 0 };
int dz[6] = { 0, 0, 0, 0 , 1, -1 };
char building[30][30][30];
int visited[30][30][30];
int L, R, C;
class pos {
public:
int z;
int x;
int y;
pos(int z, int x, int y) : z(z), x(x), y(y) {
}
};
int bfs() {
queue<pos> Q;
for (int z = 0; z < L; z++) {
for (int x = 0; x < R; x++) {
for (int y = 0; y < C; y++) {
if (building[z][x][y] == 'S') {
Q.push({ z, x, y });
visited[z][x][y] = 1;
}
}
}
}
while (!Q.empty()) {
auto cur = Q.front(); Q.pop();
if (building[cur.z][cur.x][cur.y] == 'E') { //Escaped
return visited[cur.z][cur.x][cur.y] - 1;
}
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 (nx < 0 || ny < 0 || nz < 0 || nz >= L ||nx >= R || ny >= C ) continue;
if (building[nz][nx][ny] == '#' || visited[nz][nx][ny]) continue;
visited[nz][nx][ny] = visited[cur.z][cur.x][cur.y] + 1;
Q.push({ nz, nx, ny });
}
}
return -1; //Trapped!
}
void reset() {
for (int z = 0; z < L; z++) {
for (int x = 0; x < R; x++) {
for (int y = 0; y < C; y++) {
building[z][x][y] = 0;
visited[z][x][y] = 0;
}
}
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
while (true) {
cin >> L >> R >> C;
if (L == 0 && R == 0 && C == 0) break;
for (int z = 0; z < L; z++) {
for (int x = 0; x < R; x++) {
for (int y = 0; y < C; y++) {
cin >> building[z][x][y];
}
}
}
int res = bfs();
if (res == -1) {
cout << "Trapped!\n";
}
else {
cout << "Escaped in " << res << " minute(s).\n";
}
reset();
}
return 0;
}
|
cs |
반응형
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| [백준 12851번] 숨바꼭질2 (0) | 2021.11.22 |
|---|---|
| [백준 13913번] 숨바꼭질4 (0) | 2021.11.21 |
| [백준 5014번] 스타트링크 (0) | 2021.11.19 |
| [백준 2146번] 다리 만들기 (0) | 2021.11.19 |
| [백준 5427번] 불 (0) | 2021.11.17 |