문제
상범빌딩 백준 6593
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
int L, R, C; // 층, 행, 열
int bd[35][35][35];
int vis[35][35][35]; // 거리 저장
int dx[] = {0, 0, 0, 0, 1, -1}; // 층
int dy[] = {0, 1, 0, -1, 0, 0}; // 행
int dz[] = {1, 0, -1, 0, 0, 0}; // 열
queue<pair<pair<int,int>, int>> qu; // 층, 행, 열
int exittime; // 탈출시간
bool rangecheck(int i, int j, int k){ // 층, 행, 열 유효범위 검사
return (i >=0 && i < L && j >= 0 && j < R && k >=0 && k < C);
}
void initvis(){ // 방문배열 초기화
for(int i = 0; i < 35; i++)
for(int j = 0; j < 35; j++) {
fill(vis[i][j], vis[i][j] + 35, -1);
fill(bd[i][j], bd[i][j] + 35, 0);
}
}
int bfs(){
while(!qu.empty()) {
int curx = qu.front().X.X;
int cury = qu.front().X.Y;
int curz = qu.front().Y;
qu.pop();
if(bd[curx][cury][curz] == 3) return vis[curx][cury][curz];
for (int i = 0; i < 6; i++) {
int nx = dx[i] + curx;
int ny = dy[i] + cury;
int nz = dz[i] + curz;
// 벽(1)이면 못감. 유효범위, 방문여부 확인
if (!rangecheck(nx, ny, nz) || bd[nx][ny][nz] == 1 || vis[nx][ny][nz] >= 0) continue;
vis[nx][ny][nz] = 1+vis[curx][cury][curz]; // 방문
qu.push({{nx,ny},nz});
}
}
return -1;
}
void input(){ // 입력받기
// 초기화
initvis();
while(!qu.empty()) qu.pop(); // 큐 비우기
// 입력받기
char ch;
for(int i = 0; i < L; i++) { // 층
for (int j = 0; j < R; j++) { // 행
for (int k = 0; k < C; k++) { // 열
cin >> ch;
if (ch == '#') { // 벽 1
bd[i][j][k] = 1;
} else if (ch == 'S') { // 시작 위치 2
bd[i][j][k] = 2;
vis[i][j][k] = 0;
qu.push({{i,j},k});
} else if (ch == 'E') { // 출구 3
bd[i][j][k] = 3;
}
}
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
while(1){
cin >> L >> R >> C; // 입력받기
if(L==0 && R ==0 && C==0) break; // 종료조건
input();
int result = bfs();
if(result < 0) cout << "Trapped!" << '\n';
else cout << "Escaped in "<<result << " minute(s)." << '\n';
}
return 0;
}
리뷰
문제를 주의 깊게 안읽어서 고생했다.
3차원 토마토 문제랑 거의 똑같다. 시작 위치와 탈출 위치가 정해져 있다.
vis 배열은 거리를 저장하고 방문여부를 구분하기 위해 -1로 초기화했다.
bd 배열은 1이면 벽으로 표시해서 방문하지 못하게 했다.
vis 배열에는 거리를 저장했다. 그래서 시작 위치에서는 0이다.
테스트케이스가 여러개니까 방문배열과 큐를 반드시 초기화한 다음에 bfs를 돌아야 한다.
큐에 '거리'(==이동 횟수) 를 저장하는 방법으로도 풀었다.
코드링크
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
int L, R, C; // 층, 행, 열
int bd[35][35][35];
bool vis[35][35][35];
int dx[] = {0, 0, 0, 0, 1, -1}; // 층
int dy[] = {0, 1, 0, -1, 0, 0};
int dz[] = {1, 0, -1, 0, 0, 0};
queue<pair<pair<int,int>, pair<int,int>>> qu; // 층, 행, 열, 이동횟수
bool rangecheck(int i, int j, int k){ // 층, 행, 열 유효범위 검사
return (i >=0 && i < L && j >= 0 && j < R && k >=0 && k < C);
}
void initvis(){ // 방문배열 초기화
for(int i = 0; i < 35; i++)
for(int j = 0; j < 35; j++) {
fill(vis[i][j], vis[i][j] + 35, false);
fill(bd[i][j], bd[i][j] + 35, 0);
}
}
int bfs(){
while(!qu.empty()) {
int curx = qu.front().X.X;
int cury = qu.front().X.Y;
int curz = qu.front().Y.X;
int curcnt = qu.front().Y.Y;
qu.pop();
if(bd[curx][cury][curz] == 3) return curcnt;
for (int i = 0; i < 6; i++) {
int nx = dx[i] + curx;
int ny = dy[i] + cury;
int nz = dz[i] + curz;
// 벽(1)이면 못감. 유효범위, 방문여부 확인
if (!rangecheck(nx, ny, nz) || bd[nx][ny][nz] == 1 || vis[nx][ny][nz]) continue;
vis[nx][ny][nz] = true; // 방문
qu.push({{nx,ny},{nz, curcnt+1}});
}
}
return -1;
}
void input(){ // 입력받기
// 초기화
initvis();
while(!qu.empty()) qu.pop(); // 큐 비우기
// 입력받기
char ch;
for(int i = 0; i < L; i++) { // 층
for (int j = 0; j < R; j++) { // 행
for (int k = 0; k < C; k++) { // 열
cin >> ch;
if (ch == '#') { // 벽 1
bd[i][j][k] = 1;
} else if (ch == 'S') { // 시작 위치 2
bd[i][j][k] = 2;
vis[i][j][k] = true;
qu.push({{i,j},{k,0}});
} else if (ch == 'E') { // 출구 3
bd[i][j][k] = 3;
}
}
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
while(1){
cin >> L >> R >> C; // 입력받기
if(L==0 && R ==0 && C==0) break; // 종료조건
input();
int result = bfs();
if(result < 0) cout << "Trapped!" << '\n';
else cout << "Escaped in "<<result << " minute(s)." << '\n';
}
return 0;
}