[BOJ] 6593 - 상범 빌딩

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/6593

6593번: 상범 빌딩

난이도: 골드 5

사용언어: JAVA

 

풀이

전형적으로 BFS를 사용하여 풀 수 있는 문제이며, 단 한 가지 다른 점은 일반적인 BFS 문제는 2차원 배열에서 풀이를 한다면, 위의 문제는 3차원 배열에서 풀이를 한다는 점입니다. 따라서 이동할 수 있는 장소를 표현할 때 한 차원을 더 표현해주어야 하기 때문에 조금 헷갈리는 부분이 있을 수 있을 뿐, 어렵게 접근할 필요는 없습니다.

 

import java.io.*;
import java.util.*;
 
class Main {
 
    static public class position {
        int x;
        int y;
        int z;
 
        public position(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }
 
    static Queue<position> q = new LinkedList<>();
    static char[][][] arr;
    static int L, R, C;
    static int[] dx = {-1, 0, 0, 0, 0, 1};
    static int[] dy = {0, -1, 0, 1, 0, 0};
    static int[] dz = {0, 0, -1, 0, 1, 0};
 
    public static void bfs(position p) {
        int nx, ny, nz;
        for (int i = 0; i < 6; i++) {
            nx = p.x + dx[i];
            ny = p.y + dy[i];
            nz = p.z + dz[i]; // 이동할 위치
 
            if (arr[nx][ny][nz] == '.' || arr[nx][ny][nz] == 'E') { //.이거나 E인 공간으로만 이동
                if (arr[nx][ny][nz] == '.')
                    arr[nx][ny][nz] = 'S'; // 한 번 온 곳을 다시 검사하지 않기 위해
                q.add(new position(nx, ny, nz)); // 큐에 삽입
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
 
        while (!(L == 0 && R == 0 && C == 0)) {
            arr = new char[L + 2][R + 2][C + 2];
            String s;
            int cnt = 0;
            for (int i = 1; i <= L; i++) {
                for (int j = 1; j <= R; j++) {
                    s = br.readLine();
                    for (int k = 1; k <= C; k++) {
                        arr[i][j][k] = s.charAt(k - 1);
                        if (arr[i][j][k] == 'S') { // 상범의 초기 위치 저장
                            q.add(new position(i, j, k));
                        }
                    }
                }
                s = br.readLine();
            }
 
            int q_size;
            int flag = 0;
            while (!q.isEmpty()) {
                q_size = q.size();
                for (int i = 0; i < q_size; i++) {
                    position p = q.poll();
                    if (arr[p.x][p.y][p.z] == 'E') { // E에 도달하면 종료
                        bw.write("Escaped in " + String.valueOf(cnt) + " minute(s).\n");
                        flag = 1;
                        break;
                    }
 
                   bfs(p); // 아직 E에 도달하지 못했다면, BFS 수행
                }
                if (flag == 1)
                    break;
                cnt++;
            }
            if (flag == 0) { // E에 도달하지 못하고 반복문이 종료
                bw.write("Trapped!\n");
            }
 
            st = new StringTokenizer(br.readLine());
            L = Integer.parseInt(st.nextToken());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
           q.clear(); // 다음 테스트 케이스로 넘어가기 전에 큐를 초기화
        }
        bw.flush();
        bw.close();
        br.close();
    }
}