백준 6593 - 상범 빌딩

문제

https://www.acmicpc.net/problem/6593

리뷰

BFS를 활용하여 풀 수 있는 전형적인 문제였다. 주어진 3차원 공간에서 동,서,남,북,상,하로
탐색을 진행하며 E 에 도달할 시 탐색에 걸린 시간을 반환하는 식으로 bfs 로직을
구성하였다.

유의할 점으론 3차원 배열을 활용할 때는 arr[z][y][x] 형식으로 정의해주어야
연산이 편리하다는 것과 필자의 경우 별도의 visited 배열을 활용하지 않고 기존 map의
값을 방문했을 경우 바꿔주고 진입하지 않는 식으로 구성했기에 관련하여 조건문을 명확히
해야한다는 것이었다.

bfs 로직의 시간복잡도는 인접행렬로 나타낸 그래프에서 $O(V^2)$의 형태이고 주어진
문제 조건에서 정점의 최대 개수는 $30^3$ 이나 실질적으로 모든 정점을 탐색하진 않으므로
주어진 시간 제한 조건을 무난히 통과한다.

코드

import java.util.*;

import static java.lang.Integer.parseInt;


public class Main {
    static int L, R, C;
    static char[][][] map;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        while (true) {
            StringTokenizer st = new StringTokenizer(in.nextLine());
            L = parseInt(st.nextToken());
            R = parseInt(st.nextToken());
            C = parseInt(st.nextToken());

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

            map = new char[L][R][C];

            int startX, startY, startZ;
            startX = startY = startZ = 0;

            for (int z = 0; z < L; z++) {
                for (int y = 0; y < R; y++) {
                    String line = in.nextLine();
                    for (int x = 0; x < C; x++) {
                        map[z][y][x] = line.charAt(x);
                        if (map[z][y][x] == 'S') {
                            startX = x;
                            startY = y;
                            startZ = z;
                        }
                    }
                }

                in.nextLine();
            }

            int result = bfs(startX, startY, startZ);
            sb.append(result == -1 ? "Trapped!" : "Escaped in " + result + " minute(s).").append("\n");
        }

        System.out.print(sb);
        in.close();
    }

    static int bfs(int startX, int startY, int startZ) {
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(new Node(startX, startY, startZ, 0));

        int[] px = {0, 0, 0, 0, -1, 1};
        int[] py = {0, 0, -1, 1, 0, 0};
        int[] pz = {-1, 1, 0, 0, 0, 0};

        while (!queue.isEmpty()) {
            Node current = queue.poll();

            for (int i = 0; i < px.length; i++) {
                int nx = current.x + px[i];
                int ny = current.y + py[i];
                int nz = current.z + pz[i];

                if (isValid(nx, ny, nz) && map[nz][ny][nx] != '#' && map[nz][ny][nx] != 'S') {
                    if (map[nz][ny][nx] == 'E') {
                        return current.level + 1;
                    }

                    map[nz][ny][nx] = 'S';
                    queue.offer(new Node(nx, ny, nz, current.level + 1));
                }
            }
        }

        return -1;
    }

    static boolean isValid(int x, int y, int z) {
        return x >= 0 && x < C && y >= 0 && y < R && z >= 0 && z < L;
    }

    static class Node {
        int x, y, z, level;

        public Node(int x, int y, int z, int level) {
            this.x = x;
            this.y = y;
            this.z = z;
            this.level = level;
        }
    }
}

결과