[BOJ] 상범빌딩

문제

당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다.

각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다.
당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다.
그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다.

당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까?

풀이

빌딩을 탐색하여 출구를 찾는 문제이다.
2차원으로 탐색하던 BFS와 달리 3차원으로 탐색해야 한다.
빌딩의 이동은 상, 하, 동, 서, 남, 북이 가능하다.
상 하 이동에 대한 이동은 다음과 같다.

예를 들어 다음과 같은 입력 있다고 하자.

S#
#E

.#
..

그렇다면 빌딩은 다음과 같은 그림으로 생긴다.

필자는 그림은 매우 못그리니 양해 부탁한다.

 

 

상, 하 이동은 1에서 2으로의 이동, 3에서 4의 이동을 말한다.
따라서 대각선을 제외한 모든 방향에서 탐색을 진행해야 한다.

3차원의 map과 visited를 만들어서 일반 BFS처럼 탐색을 진행하였다.

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
    static int[] x_loc = {1, -1, 0, 0, 0, 0};
    static int[] y_loc = {0, 0, 1, -1, 0, 0};
    static int[] floor_loc = {0, 0, 0, 0, 1, -1};
    static int L;
    static int R;
    static int C;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true) {
            String[] str = br.readLine().split(" ");
            int answer = 0;
            L = Integer.parseInt(str[0]);
            R = Integer.parseInt(str[1]);
            C = Integer.parseInt(str[2]);
            String[][][] map = new String[L][R][C];
            boolean[][][] visited = new boolean[L][R][C];

            if (L == 0 && R == 0 && C == 0) {
                break;
            }

            for (int i = 0; i < L; i++) {
                for (int j = 0; j < R; j++) {
                    str = br.readLine().split("");
                    for (int k = 0; k < C; k++) {
                        map[i][j][k] = str[k];
                    }
                }
                br.readLine();
            }

            for (int i = 0; i < L; i++) {
                for (int j = 0; j < R; j++) {
                    for (int k = 0; k < C; k++) {
                        if (map[i][j][k].equals("S")) {
                            answer = bfs(i, j, k, visited, map);
                        }
                    }
                }
            }

            if (answer != 0) {
                System.out.println("Escaped in " + (answer + 1) + " minute(s).");
            } else {
                System.out.println("Trapped!");
            }
        }
    }

    static int bfs(int floor, int x, int y, boolean[][][] visited, String[][][] map) {
        int count = 0;
        Queue<Loc> queue = new LinkedList<>();
        boolean flag = false;
        queue.add(new Loc(floor, x, y, 0));
        visited[floor][x][y] = true;

        while(!queue.isEmpty()) {
            Loc loc = queue.poll();
            for(int i = 0; i < 6; i++) {
                int nextFloor = loc.floor + floor_loc[i];
                int nextX = loc.x + x_loc[i];
                int nextY = loc.y + y_loc[i];

                if (check(nextX, nextY, nextFloor, visited)) {
                    if (map[nextFloor][nextX][nextY].equals(".")) {
                        visited[nextFloor][nextX][nextY] = true;
                        queue.add(new Loc(nextFloor, nextX, nextY, loc.count + 1));
                    } else if (map[nextFloor][nextX][nextY].equals("E")) {
                        flag = true;
                        count = loc.count;
                        break;
                    }
                }
            }

            if (flag) {
                break;
            }
        }

        return count;
    }

    static boolean check(int x, int y, int floor, boolean[][][] visited) {
        return (x >= 0 && x < R) && (y >= 0 && y < C) && (floor >= 0 && floor < L) && !visited[floor][x][y];
    }

    static class Loc {
        int floor;
        int x;
        int y;
        int count;

        public Loc(int floor, int x, int y, int count) {
            this.floor = floor;
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
}

https://github.com/Win-9/Algorism/tree/main/BOJ/%EC%83%81%EB%B2%94%EB%B9%8C%EB%94%A9