[BOJ] 6593. 상범빌딩 - BFS

[BOJ] 6593. 상범빌딩 - BFS

제출일 : 2019-09-23

문제 풀이 시간 : 1H

난이도 : ★★★

Problem

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

Input

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.

그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다.

Output

각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 다음과 같이 출력한다.

Escaped in x minute(s).

여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다.

만일 탈출이 불가능하다면, 다음과 같이 출력한다.

Trapped!

Example

input

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

output

Escaped in 11 minute(s).
Trapped!

Solution & Inpression

2차원 배열의 BFS문제들과 비슷하게 풀어나갔다. 다만 탐색을 6방향으로 해야 문제를 해결할 수 있다.

Code

언어 : JAVA

메모리 : 18,104kb

실행시간 : 148ms

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

public class Main {
    static int L, R, C;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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;

            char[][][] building = new char[L][R][C];
            boolean visit[][][] = new boolean[L][R][C];
            Queue<int[]> q = new LinkedList<int[]>();
            for (int k = 0; k < L; k++) {
                for (int i = 0; i < R; i++) {
                    String str = br.readLine();
                    for (int j = 0; j < C; j++) {
                        char cur = str.charAt(j);
                        building[k][i][j] = cur;
                        if (cur == 'S') {
                            q.offer(new int[] { k, i, j, 0 });
                            visit[k][i][j] = true;
                        }
                    }
                }
                br.readLine();
            } // 입력 끝

            int[] dk = { -1, 1, 0, 0, 0, 0 };
            int[] dx = { 0, 0, -1, 1, 0, 0 };
            int[] dy = { 0, 0, 0, 0, -1, 1 };
            int res = Integer.MAX_VALUE;

            while (!q.isEmpty()) {
                int[] cur = q.poll();
                 //System.out.println(Arrays.toString(cur));
                if (building[cur[0]][cur[1]][cur[2]] == 'E') {
                    res = (cur[3] > res) ? res : cur[3];
                    continue;
                }
                for (int k = 0; k < 6; k++) {
                    int l = cur[0] + dk[k];
                    int x = cur[1] + dx[k];
                    int y = cur[2] + dy[k];
                    if (range(l, x, y) && !visit[l][x][y] && building[l][x][y] != '#') {
                        visit[l][x][y] = true;
                        q.offer(new int[] { l, x, y, (cur[3] + 1) });
                    }
                }
            }
            System.out.println((res == Integer.MAX_VALUE) ? "Trapped!" : "Escaped in " + res + " minute(s).");

        }
    }

    private static boolean range(int l, int x, int y) {
        if (0 <= l && l < L && 0 <= x && x < R && 0 <= y && y < C)
            return true;
        return false;
    }
}