[백준 6593] 상범빌딩

www.acmicpc.net/problem/6593

6593번: 상범 빌딩

 

문제 풀이
: bfs를 사용하는 문제이며 3차원 배열을 사용한다는 점에서 토마토와 매우 유사하다.

실수 했던 것은 .만 갈 수 있게 만들어서 목적지에 도달하지 못했다는 점..

 

입력을 받으면서 출발지를 큐에 바로 푸쉬하고 도착지는 따로 저장해 놓는다.

큐의 프론트 값이 도착지와 동일하면 함수를 종료한다. 이 때 큐는 재사용하므로 큐도 비워줘야 한다.

 

#include <stdio.h>
#include <queue>
#include <string.h>
#define MAX 31
using namespace std;

struct Move
{
  int z, y, x;
};

char map[MAX][MAX][MAX];
int path[MAX][MAX][MAX];
int L, R, C;

int dl[6] = {0, 0, 0, 0, 1, -1};
int dr[6] = {1, -1, 0, 0, 0, 0};
int dc[6] = {0, 0, -1, 1, 0, 0};
queue<Move> q;

int main(void)
{
  while (1)
  {
    scanf("%d%d%d", &L, &R, &C);

    if (!L && !R && !C)
    {
      break;
    }
    int dstL, dstR, dstC;
    char tmp[MAX];
    for (int l = 0; l < L; l++)
    {
      for (int r = 0; r < R; r++)
      {
        scanf("%s", tmp);
        for (int c = 0; c < C; c++)
        {
          map[l][r][c] = tmp[c];
          if (map[l][r][c] == 'S')
          {
            q.push({l, r, c});
          }

          if (map[l][r][c] == 'E')
          {
            dstL = l;
            dstR = r;
            dstC = c;
          }
        }
      }
      getchar();
    }

    memset(path, 0, sizeof(path));
    bool flag = false;
    int minute;
    while (!q.empty())
    {
      Move fr = q.front();
      if (fr.z == dstL && fr.y == dstR && fr.x == dstC)
      {
        flag = true;
        minute = path[fr.z][fr.y][fr.x];
        break;
      }

      q.pop();

      for (int i = 0; i < 6; i++)
      {
        int nZ = fr.z + dl[i];
        int nY = fr.y + dr[i];
        int nX = fr.x + dc[i];

        if (nZ > -1 && nY > -1 && nX > -1 &&
            nZ < L && nY < R && nX < C &&
            !path[nZ][nY][nX] && map[nZ][nY][nX] != '#')
        {
          path[nZ][nY][nX] = path[fr.z][fr.y][fr.x] + 1;
          map[nZ][nY][nX] == '#';
          q.push({nZ, nY, nX});
        }
      }
    }

    while (!q.empty())
    {
      q.pop();
    }

    if (flag)
    {
      printf("Escaped in %d minute(s).\n", minute);
    }
    else
    {
      printf("Trapped!\n");
    }
  }
  return 0;
}