6593 : 상범 빌딩

출처 : https://www.acmicpc.net/problem/6593

---

문제

당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져 있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동, 서, 남, 북, 상, 하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥 면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다. 당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까?

입력

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다. 그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다. 시작 지점과 출구는 항상 하나만 있다.

출력

각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 Escaped in x minute(s), 만일 탈출이 불가능하다면, Trapped! 을 출력한다. 여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다.

---

접근

• 상하좌우를 탐색하던 일반적인 BFS에 위, 아래층이라는 개념이 추가되었다. 
• 3차원 배열을 이용한다. 
• 층 간 이동이 가능한지, 같은 층에서 상하좌우로 이동이 가능한지, 이렇게 두 부분으로 나누어 탐색을 한다. 
• BFS 함수 내의 while문 내부에서 return 되지 않는다면, 탈출 불가로 판단하여, -1을 return 한다. 

---

코드

import java.io.*;
import java.util.*;
 
class Escaped {
    int x, y, z;
 
    public Escaped(int x, int y, int z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }
}
 
public class Main {
    static int L, R, C;
    static int[][][] map;
    static int[][][] visit;
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, -1, 0, 1 };
    static int[] dz = { -1, 1 };
 
    public static int BFS(Escaped e) {
        Queue<Escaped> q = new LinkedList<Escaped>();
        visit[e.x][e.y][e.z] = 1;
        q.add(e);
 
        while (!q.isEmpty()) {
            Escaped tmp = q.poll();
            int X = tmp.x;
            int Y = tmp.y;
            int Z = tmp.z;
 
            // 위, 아래층 탐색
            for (int i = 0; i < 2; i++) {
                int nextZ = Z + dz[i];
                if (nextZ >= 0 && nextZ < L) {
                    if (map[X][Y][nextZ] == 2) { // 방문 예정 지점이 탈출구라면,
                        return visit[X][Y][Z];
                    }
                    if (map[X][Y][nextZ] == 0 && visit[X][Y][nextZ] == 0) { // 방문 예정 지점이 방문 가능 지점이라면,
                        q.add(new Escaped(X, Y, nextZ));
                        visit[X][Y][nextZ] = visit[X][Y][Z] + 1;
                    }
                }
            }
 
            // 상, 하, 좌, 우 탐색
            for (int i = 0; i < 4; i++) {
                int nextX = X + dx[i];
                int nextY = Y + dy[i];
                if (nextX >= 0 && nextY >= 0 && nextX < R && nextY < C) {
                    if (map[nextX][nextY][Z] == 2) { // 방문 예정 지점이 탈출구라면,
                        return visit[X][Y][Z];
                    }
                    if (map[nextX][nextY][Z] == 0 && visit[nextX][nextY][Z] == 0) { // 방문 예정 지점이 방문 가능 지점이라면,
                        q.add(new Escaped(nextX, nextY, Z));
                        visit[nextX][nextY][Z] = visit[X][Y][Z] + 1;
                    }
                }
            }
        }
        return -1;
    }
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        Queue<Integer> ans = new LinkedList<Integer>(); // 답을 저장할 queue
 
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
 
            L = Integer.parseInt(st.nextToken());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
 
            if (L == 0 && R == 0 && C == 0) { // 모두 0일 때 종료
                break;
            }
 
            map = new int[R][C][L];
            visit = new int[R][C][L];
            int x = 0, y = 0, z = 0; // 시작 지점의 좌표
 
            for (int k = 0; k < L; k++) {
                for (int i = 0; i < R; i++) {
                    char[] c = br.readLine().toCharArray();
                    for (int j = 0; j < C; j++) {
                        if (c[j] == 'S') { // 출발지
                            map[i][j][k] = 1;
                            x = i;
                            y = j;
                            z = k;
                        } else if (c[j] == 'E') { // 탈출
                            map[i][j][k] = 2;
                        } else if (c[j] == '#') { // 벽
                            map[i][j][k] = -1;
                        } else {
                            map[i][j][k] = 0;
                        }
                    }
                }
                st = new StringTokenizer(br.readLine()); // 공백
            }
            int tmp = BFS(new Escaped(x, y, z));
            ans.add(tmp);
        }
 
        while (!ans.isEmpty()) {
            int tmp = ans.poll();
            if (tmp == -1) {
                bw.write("Trapped!\n");
            } else {
                bw.write("Escaped in " + tmp + " minute(s).\n");
            }
        }
 
        bw.flush();
        br.close();
 
    }
 
}