상범빌딩 백준 6593번 c++

문제

상범빌딩 백준 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;
}