[백준] 6593번 상범 빌딩

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q1000/Q6593.java

상범이가 빌딩을 탈출할 수 있다면 양식에 맞춰 최단 시간을 출력하고 탈출할 수 없다면 탈출 불가일 때의 
문자를 출력하여라.

처음 생각

이전에 풀었던 문제인 [백준] 7569번 토마토 와 비슷하게 풀어볼 수 있는 문제이다.

다음 생각

여러개의 케이스가 주어지고 입력이 조금 특이하게 라인 단위로 띄워져 있기 때문에 입력을 받을 때 이부분을 조심해야한다.

다다음 생각

3차원 적으로 생각을 해야하기에 3차원 배열을 생성해서 길을 찾아갈 수 있도록 해주었다.

▶ 다차원 배열은 메모리를 많이 잡아먹기 때문에 따로 visited 배열을 만들어 주지않고, 원본 배열을 갈 수 있는 길인 '.'을 '#'로 바꿔주어 방문처리를 해주었다.

다다다음 생각

3차원 배열로 빌딩의 상태를 모두 받았다면 queue를 이용해서 BFS 탐색을 통해 최단거리로 탈출구를 만날 수 있는가를 판단해주었고, BFS 탐색이 끝나서 while문을 빠져나온 경우는 탈출에 실패한 경우이므로 탈출 불가를 출력해주었다.

다다다다음 생각

배열로 쓸 queue를 생성할 때는 맵의 크기가 최대 30*30*30이므로 그보다 큰 값으로 적당히 만들어 주었다.

방안

1) Java 풀이

package baekjoon.q1000;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Q6593 {
    static int l,r,c;
    static int[][] q = new int[29000][3];
    static int[][][] arr = new int[30][30][30];
    static int[] dx = {1,0,-1,0,0,0};
    static int[] dy = {0,1,0,-1,0,0};
    static int[] dz = {0,0,0,0,1,-1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
xx:        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) {
                break;
            }
            int sx = 0,sy = 0, sz = 0;
            for(int i=0;i<l;i++) {
                for(int j=0;j<r;j++) {
                    String t = br.readLine();
                    for(int k=0;k<c;k++) {
                        char tt = t.charAt(k);
                        arr[i][j][k] = tt;
                        if(tt=='S') {
                            sx = j;
                            sy = k;
                            sz = i;
                        }
                    }
                }
                br.readLine();
            }
            int front = 0,rear = 0;
            q[++rear][0] = sx;
            q[rear][1] = sy;
            q[rear][2] = sz;
            int time = 0;
            while(front<rear) {
 
                time++;
                int size = rear-front;
                for(int i=0;i<size;i++) {
                    int x = q[++front][0];
                    int y = q[front][1];
                    int z = q[front][2];
 
                    for(int j=0;j<6;j++) {
                        int tx = x+dx[j];
                        int ty = y+dy[j];
                        int tz = z+dz[j];
                        if(tx<0||ty<0||tz<0||tx>=r||ty>=c||tz>=l) continue;
                        if(arr[tz][tx][ty]!='#') {
                            if(arr[tz][tx][ty]=='E') {
                                sb.append(String.format("Escaped in %d minute(s).", time)).append('\n');
                                continue xx;
                            }
                            q[++rear][0] = tx;
                            q[rear][1] = ty;
                            q[rear][2] = tz;
                            arr[tz][tx][ty] = '#';
                        }
                    }
                }
            }// end of while(front<rear)
            sb.append("Trapped!").append('\n');
        }// end of while(true)
        System.out.println(sb);
    }// end of main
} // end of class