[백준 6593] 상범 빌딩

 

 

최단 시간을 구해야하므로 BFS 로 접근한다.

지나갈 수 있는 길을 탐색하면 되는데 배열이 3차원이라는 데에 주의해야 한다.

 

S

.

.

.

.

#

#

#

#

#

#

#

#

#

#

.

#

#

#

.

#

#

#

#

#

#

#

#

#

#

.

#

#

.

.

#

#

.

#

#

#

.

#

#

#

#

#

#

.

#

#

#

.

.

.

#

#

#

#

E

 

예제로 풀이해보자.

왼쪽부터 1, 2, 3층이다.

 

S

.

.

.

.

#

#

#

#

#

#

#

#

#

#

.

#

#

#

.

#

#

#

#

#

#

#

#

#

#

.

#

#

.

.

#

#

.

#

#

#

.

#

#

#

#

#

#

.

#

#

#

.

.

.

#

#

#

#

E

 

한칸 이동했을때이다. 가까운 동서남북상하로 이동했다.

 

S

.

.

.

.

#

#

#

#

#

#

#

#

#

#

.

#

#

#

.

#

#

#

#

#

#

#

#

#

#

.

#

#

.

.

#

#

.

#

#

#

.

#

#

#

#

#

#

.

#

#

#

.

.

.

#

#

#

#

E

 

2칸 이동했다. 길이 하나이니 쭉 이동해보자.

 

S

.

.

.

.

#

#

#

#

#

#

#

#

#

#

.

#

#

#

.

#

#

#

#

#

#

#

#

#

#

.

#

#

.

.

#

#

.

#

#

#

.

#

#

#

#

#

#

.

#

#

#

.

.

.

#

#

#

#

E

 

8칸 이동했다. 이전까지는 다른층으로 가는 길이 없었는데 처음으로 2층의 길과 이어졌다.

 

S

.

.

.

.

#

#

#

#

#

#

#

#

#

#

.

#

#

#

.

#

#

#

#

#

#

#

#

#

#

.

#

#

.

.

#

#

.

#

#

#

.

#

#

#

#

#

#

.

#

#

#

.

.

.

#

#

#

#

E

 

9칸 이동했다. 2층에 진입하여 BFS 를 탐색을 또 시작한다.

 

S

.

.

.

.

#

#

#

#

#

#

#

#

#

#

.

#

#

#

.

#

#

#

#

#

#

#

#

#

#

.

#

#

.

.

#

#

.

#

#

#

.

#

#

#

#

#

#

.

#

#

#

.

.

.

#

#

#

#

E

 

10칸 이동했다. 2층 (4, 5) 에서 3층으로 가는 길이있다.

 

S

.

.

.

.

#

#

#

#

#

#

#

#

#

#

.

#

#

#

.

#

#

#

#

#

#

#

#

#

#

.

#

#

.

.

#

#

.

#

#

#

.

#

#

#

#

#

#

.

#

#

#

.

.

.

#

#

#

#

E

 

11칸 째에 도착했다.

 

 

public class Main {
    
    static int l = 1;
    static int r = 1;
    static int c = 1;
    static char[][][] a;
    static int distance[][][];
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        while(true) {
            l = scan.nextInt();
            r = scan.nextInt();
            c = scan.nextInt();
            if(l == 0 && r == 0 && c == 0) break;
            int sl = 0, sr = 0, sc = 0, gl = 0, gr = 0, gc = 0;
            a = new char[l][r][c];
            for(int i=0; i<l; i++) {
                for(int j=0; j<r; j++) {
                    a[i][j] = scan.next().toCharArray();
                    for(int k=0; k<c; k++) {
                        if(a[i][j][k] == 'S') {
                            sl = i;
                            sr = j;
                            sc = k;
                        }
                        if(a[i][j][k] == 'E') {
                            gl = i;
                            gr = j;
                            gc = k;
                        }
                    }
                }
            }
            bfs(sl, sr, sc);
            System.out.println(distance[gl][gr][gc] == 0 ? "Trapped!" : "Escaped in " + distance[gl][gr][gc] + " minute(s).");
        }
    }
    
    public static void bfs(int x, int y, int z) {
        boolean visited[][][] = new boolean[l][r][c];
        distance = new int[l][r][c];
        Queue<Pair> q = new LinkedList<Pair>();
        
        q.offer(new Pair(x, y, z));
        distance[x][y][z] = 0;
        visited[x][y][z] = true;
        int ml[] = {0, 0, 0, 0, -1, 1};
        int mr[] = {0, 0, 1, -1, 0, 0};
        int mc[] = {1, -1, 0, 0, 0, 0};
        while(!q.isEmpty()) {
            Pair point = q.poll();
            int pl = point.getX();
            int pr = point.getY();
            int pc = point.getZ();
            for(int i=0; i<6; i++) {
                int nl = pl + ml[i];
                int nr = pr + mr[i];
                int nc = pc + mc[i];
                if(0 <= nl && nl < l && 0 <= nr && nr < r && 0 <= nc && nc < c) {
                    if((a[nl][nr][nc] == '.' || a[nl][nr][nc] == 'E') && !visited[nl][nr][nc]) {
                        visited[nl][nr][nc] = true;
                        q.offer(new Pair(nl, nr, nc));
                        distance[nl][nr][nc] = distance[pl][pr][pc] + 1;
                    }
                }
            }
        }
    }
    
    static class Pair {
        int x;
        int y;
        int z;
        
        Pair(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
        
        int getX() {
            return x;
        }
        int getY() {
            return y;
        }
        int getZ() {
            return z;
        }
    }
}