Baekjoon 6593 상범 빌딩 JAVA

6593번: 상범 빌딩

문제

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

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

 

조건

[입력]

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

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

 

[출력]

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

Escaped in x minute(s).

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

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

Trapped!

 

풀이

해당 문제는 전형적인 bfs dfs 문제였다 다만 입력 데이터가 3차원 배열로 주어지기 때문에 해당 부분만 잘 체크하면 되는 문제다.

나는 bfs를 이용하여 해결했으며 로직은 아래와 같다.

 

1. 입력 처리한다. 

2. S에 대해서 좌표값을 큐에 저장하고 방문 처리한다

3. bfs를 돌린다.

    1. 큐에서 빼낸곳이 E면 횟수를 리턴한다.

    2. 6방향에 대해 체크한다.

        1. 배열 범위를 벗어나면 다음 반복을 진행한다.

        2. 이미 방문했거나 금이면 다음 반복을 진행한다.

        3. 큐에 좌표값을 넣고 방문 처리한다.

    3. 큐가 비면 -1을 리턴한다.

4. bfs의 리턴 값을 통해 성공 및 실패에 대한 출력 처리를 한다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int L, R, C, dy[]={-1,1,0,0,0,0}, dx[]={0,0,-1,1,0,0}, dh[]={0,0,0,0,-1,1}; // 3차원 좌표 체크
    static char[][][] map;
    static boolean[][][] visit;
    static Queue<Node> queue;
    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 && R==0 && C==0)
                break;

            map = new char[L][R][C];
            visit = new boolean[L][R][C];
            queue = new LinkedList<>();

            for (int k = 0; k < L; k++) {
                for (int i = 0; i < R; i++) {
                    map[k][i] = br.readLine().toCharArray(); // map 에 데이터 넣어줌
                    for (int j = 0; j < C; j++) {
                        if(map[k][i][j] == 'S'){ // 시작 좌표 큐에 넣고 방문 체크함
                            queue.add(new Node(k,i,j,0));
                            visit[k][i][j] = true;
                        }
                    }
                }
                br.readLine(); // 한줄쓰기
            }
            int ans = bfs(); // bfs 돌림
            if(ans == -1) // 실패한경우
                System.out.println("Trapped!");
            else // 성공한경우
                System.out.println("Escaped in "+ans+" minute(s).");
        }
    }

    private static int bfs() {
        while (!queue.isEmpty()) {
            Node n = queue.poll();
            if (map[n.d][n.y][n.x] == 'E') // 도착하면 리턴
                return n.n;

            for (int i = 0; i < 6; i++) {
                int ny = n.y + dy[i];
                int nx = n.x + dx[i];
                int nh = n.d + dh[i];
                if (ny < 0 || nx < 0 || nh < 0 || ny >= R || nx >= C || nh >= L)
                    continue; // 배열 범위 벗어날경우
                if (visit[nh][ny][nx] || map[nh][ny][nx] == '#')
                    continue; // 방문했거나 금인경우
                queue.add(new Node(nh, ny, nx, n.n + 1));
                visit[nh][ny][nx] = true;
            }
        }
        return -1;
    }

    static class Node{
        int d, y, x, n;
        Node(int d, int y , int x, int n){
            this.d = d;
            this.y = y;
            this.x = x;
            this.n = n;
        }
    }
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드