6593번: 상범 빌딩
당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어
www.acmicpc.net
1. 풀이방법
- 3차원배열을 이용해야할 뿐 기초적인 BFS 문제입니다
- 범위검사와 BFS, 그리고 E에 도달하지 못했는데 큐가 비어있다면 더이상 갈 곳이 없는 것이므로
- 종료조건을 출력하고 나가면 됩니다.
2. 주의사항
- 구현에 몰두해서 짜다보니 메모리 초과가 떴는데 왜 그런가 봤더니 방문체크를 큐에서 꺼낼 때 하고 있었습니다.
- 그럴경우, 여러정점에서 동시방문하고자 할 수 있기 때문에 문제가 발생할 수 있습니다.
- BFS를 구현할 때는 방문체크를 큐에 넣을 떄 해줍시다.
3.나의코드
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
int L, R, C;
int seconds;
char sangbumbuilding[31][31][31];
bool visit[31][31][31];
int dx[6] = { 1,-1,0,0,0,0 }; //6방향 탐색
int dy[6] = { 0,0,1,-1,0,0 };
int dz[6] = { 0,0,0,0,1,-1 };
struct area {
int x, y, z;
};
queue<area> tmpq;
area S;
area E;
area tmpa, tmparea;
bool inputs() {
cin >> L >> R >> C;
if (L == 0 && R == 0 && C == 0) return true;
for (int i = 1; i <= L; i++) {
for (int j = 1; j <= R; j++) {
for (int k = 1; k <= C; k++) {
visit[i][j][k] = false;
cin >> sangbumbuilding[i][j][k];
if(sangbumbuilding[i][j][k]=='S'){
S.x = i; S.y = j; S.z = k;
}
if (sangbumbuilding[i][j][k] == 'E') {
E.x = i; E.y = j; E.z = k;
}
}
}
}
return false;
}
void bfs(area s) {
tmpq.push(s);
while (1) {
if (tmpq.empty()) { cout << "Trapped!" << "\n"; return; }
int tmpsize = tmpq.size();
while(tmpsize--) { //1초당
tmpa = tmpq.front();
tmpq.pop();
if (tmpa.x == E.x &&tmpa.y == E.y&&tmpa.z == E.z) {
cout << "Escaped in "<<seconds<<" minute(s)."<<"\n"; return;
}
for (int i = 0; i < 6; i++) { //6방향탐색
//범위 검사
if (tmpa.x + dx[i] >= 1 && tmpa.x + dx[i] <= L && tmpa.y + dy[i] >= 1 && tmpa.y + dy[i] <= R && tmpa.z + dz[i] >= 1 && tmpa.z + dz[i] <= C) {
if (sangbumbuilding[tmpa.x + dx[i]][tmpa.y + dy[i]][tmpa.z + dz[i]] == '.'|| sangbumbuilding[tmpa.x + dx[i]][tmpa.y + dy[i]][tmpa.z + dz[i]] == 'E') {
if (visit[tmpa.x + dx[i]][tmpa.y + dy[i]][tmpa.z + dz[i]] == false) {
tmparea.x = tmpa.x + dx[i]; tmparea.y = tmpa.y + dy[i]; tmparea.z = tmpa.z + dz[i];
visit[tmparea.x][tmparea.y][tmparea.z] = true;
tmpq.push(tmparea);
}
}
}
}
}
seconds++;
}
}
void resetqueue() {
while (1) {
if (tmpq.empty()) return;
tmpq.pop();
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
while (1) {
resetqueue();
if(inputs()) break;
seconds = 0;
bfs(S);
}
return 0;
}'알고리즘 문제풀이 > DFS와 BFS' 카테고리의 다른 글
| 백준 1697 [C++] (0) | 2020.12.20 |
|---|---|
| 백준 16397 [C++] (0) | 2020.12.18 |
| 백준 15684 [C++] (0) | 2020.12.09 |
| 백준 15683 [C++] (0) | 2020.12.08 |
| 백준 11404 [C++] ,플로이드 워셜 (0) | 2020.10.26 |
