[Java][자바][백준][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).

여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다.

만일 탈출이 불가능하다면, 다음과 같이 출력한다.

Trapped!

생각

허허..또 문제를 다시 보니 틀리게 만들었는데 백준에서는 통과를 해버렸다..! Trapped가 떠야하는 상황에서도 탈출한다고 되었지만 테스트케이스의 부족인지 통과를 해버렸다. 

 

만약 히든 테스트케이스가 주어지지 않는 코딩테스트였다면 바로 떨어졌을 것이다. 정신차리고 문제를 풀어야겠다.

 

코드가 복잡해져서 주석에 자세한 설명을 적도록 하겠다!

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    //static 변수와 이동에 대한 변수인 m (move)을 설정해준다.
    static int L;
    static int R;
    static int C;
    static char[][][] map;
    static boolean[][][] visited;
    static int[] dx = {-1, 1, 0, 0, 0, 0};
    static int[] dy = {0, 0, -1, 1, 0, 0};
    static int[] dz = {0, 0, 0, 0, -1, 1};
    static int m = 0;
    //실제 end 좌표와 나의 my_end 좌표를 각각 설정해준다.
    //만약 bfs가 끝났을 때 end = my_end가 아니라면 탈출을 하지 못한 것이다.
    static int end_i, end_j, end_k;
    static int my_end_i = -1; 
    static int my_end_j = -1;
    static int my_end_k = -1;
 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            
        while(true) {
            int start_i = 0;
            int start_j = 0;
            int start_k = 0;
            String str = br.readLine();
            if(str.length() == 0) str = br.readLine();
            String[] LRC = str.split(" ");
            L = Integer.parseInt(LRC[0]);
            R = Integer.parseInt(LRC[1]);
            C = Integer.parseInt(LRC[2]);
            
            if(L==0 && R==0 && C==0) {
                break;
            }
 
            map = new char[L][R][C];
            visited = new boolean[L][R][C];
 
            for(int k=0; k<map.length; k++) {
                for(int i=0; i<map[0].length; i++) {
                    char[] arr = br.readLine().toCharArray();
                    if(arr.length == 0) arr = br.readLine().toCharArray();
                    for(int j=0; j<map[0][0].length; j++) {
                        map[k][i][j] = arr[j];
                        //'S'이면 시작점을 정하고, 'E'이면 종료점을 정해준다.
                        // 입력을 해주면서 설정해야 불필요한 연산이 없다.
                        if(map[k][i][j] == 'S') {
                            start_i = k;
                            start_j = i;
                            start_k = j;
                        } else if(map[k][i][j] == 'E') {
                            end_i = k;
                            end_j = i;
                            end_k = j;
                        }
                    }
                }
            }
            
            bfs(new dot(start_i, start_j,start_k));
            //my_end = end가 같아야 탈출에 성공한 것이다.            
            if(my_end_i == end_i && my_end_j == end_j && my_end_k == end_k) {
                System.out.println("Escaped in "+ (m-1) +" minute(s).");
            } else {
                System.out.println("Trapped!");
            }
            //my_end와 m을 0으로 초기화시킨다.
            my_end_i = 0;
            my_end_j = 0;
            my_end_k = 0;
            m = 0;
        }
 
    }
    
    static void bfs(dot d) {
        Queue<dot> q = new LinkedList<dot>();
        q.add(d);
        visited[d.i][d.j][d.k] = true;
        
        loop: while(!q.isEmpty()) {
            int size = q.size();
            
            for(int i=0; i<size; i++) {
                dot t = q.remove();
                
                //'E'에 도착하면 my_end를 현재 좌표로 설정해준다.
                //만약 'E'에 도착하지 못하면 계속 -1로 유지될 것이다.
                if(map[t.i][t.j][t.k] == 'E') {
                    m++;
                    my_end_i = t.i;
                    my_end_j = t.j;
                    my_end_k = t.k;
                    break loop;
                }
                
                for(int j=0; j<6; j++) {
                    int i2 = t.i + dz[j];
                    int j2 = t.j + dx[j];
                    int k2 = t.k + dy[j];
                    
                    if(i2>=0 && i2<L && j2>=0 && j2<R && k2>=0 && k2<C &&
                            map[i2][j2][k2] != '#' && !visited[i2][j2][k2]) {
                        q.add(new dot(i2,j2,k2));
                        visited[i2][j2][k2] = true;
                    }
                    
                }
            }
            m++;
        }
    }
 
}
 
class dot {
    int i;
    int j;
    int k;
    
    public dot(int i,int j, int k) {
        this.i = i;
        this.j = j;
        this.k = k;
    }
}