[백준] 6593 상범 빌딩(Java)

문제링크

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

문제분석

• S 위치에서 출발해 E 위치에 도달하는 최단 시간
• 이동 방법
  • 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동

입력

• 여러개의 테스트 케이스가 입력됨
• 각 테스트 케이스
  • L : 빌딩층수(1 ≤ L ≤ 30)
  • R : 한층의 행 개수 (1 ≤ R ≤ 30)
  • C : 한층의 열 개수 (1 ≤ C ≤ 30)
  • 빌딩 정보
    • '#' : 막혀있는 칸
    • '.' : 지나갈 수 있는 칸
    • 'S' : 시작 지점
    • 'E' : 출구
• 입력의 끝 : L, R, C 모두 0일 때

출력

• 각 테스트 케이스에 대한 답 출력
  • x초 안에 탈출 가능 시 : Escaped in x minute(s).
  • 탈출이 불가능 : Trapped!

풀이

• 빌딩을 3차원 배열로 선언한다.

static char[][][] building; //높이, 행, 열 순서

• 큐에 넣을 Point 클래스 선언

class Point{
    int cnt,height, r, c;
}

• 동,서,남,북,상,하의 변위

int[] dh = {0, 0, 0, 0, 1, -1};
int[] dr = {0, 0, 1, -1, 0, 0};
int[] dc = {1, -1, 0, 0, 0, 0};

• 시작 위치를 큐에 넣고 BFS 탐색
  1. 큐 선언
  2. 큐에 시작 위치 삽입
  3. E 위치에 도달 or 큐가 빌때까지 반복
     • E 위치인지 확인
       • E위치이면, cnt값 반환
     • 동서남북 상하 탐색
       • 범위 벗어남 or 이미 방문 or 막혀있는지 확인
       • 모든 조건을 통과하면 큐에 삽입

전체 코드

import java.util.*;

//위치를 표현할 클래스 Point 선언
class Point{
    int cnt,height, r, c;

    public Point(int cnt, int height, int r, int c) {
        this.cnt = cnt;
        this.height = height;
        this.r = r;
        this.c = c;
    }
}

public class Main {
    // 동,서,남,북,상,하의 변위
    static int[] dh = {0, 0, 0, 0, 1, -1};
    static int[] dr = {0, 0, 1, -1, 0, 0};
    static int[] dc = {1, -1, 0, 0, 0, 0};

    static int L, R, C;
    static char[][][] building;

    static Point start; //출발 위치를 저장할 변수

    static Queue<Point> queue; //BFS에 사용할 큐
    static boolean[][][] ch; //BFS에 사용할 체크 배열

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

        while(true){
            L = scanner.nextInt();
            R = scanner.nextInt();
            C = scanner.nextInt();

            if(L==0 && R==0 && C==0) break;//종료 조건

            init();//각 테스트 케이스에서 사용할 변수 초기화

            for(int i=0; i<L; i++){
                for(int j=0; j<R; j++){
                    String str = scanner.next();
                    for(int k=0; k<C; k++){
                        building[i][j][k] = str.charAt(k);
                        //입력 중 'S'를 만나면 start 변수에 저장
                        if(building[i][j][k] == 'S') start = new Point(0,i, j, k);
                    }
                }
            }

            //너비 우선 탐색
            int answer = bfs();

            if(answer ==-1){ // 탈출 불가 시
                System.out.println("Trapped!");
            }else{ //탈출 가능 시
                System.out.println("Escaped in "+ answer +" minute(s).");
            }
        }
    }

    private static int bfs() { //너비 우선 탐색
        int answer = -1;
        //시작 위치를 큐에 넣는다.
        ch[start.height][start.r][start.c] = true;
        queue.offer(start);

        while(!queue.isEmpty()){
            Point current = queue.poll();
            //종료 조건
            if(building[current.height][current.r][current.c]=='E'){
                answer = current.cnt;
                break;
            }else{
                for(int i=0; i<6; i++){ //동서남북상하를 탐색
                    int n_height = current.height+dh[i];
                    int n_r = current.r + dr[i];
                    int n_c = current.c + dc[i];

                    //범위를 벗어나는가?
                    if(n_height<0 || n_height>=L || n_r<0 || n_r>=R || n_c<0 || n_c>=C) continue;
                    //이미 방문 했거나 막혔는가?
                    if(ch[n_height][n_r][n_c]==true || building[n_height][n_r][n_c]=='#') continue;

                    //조건을 충족하면 큐에 넣는다.
                    ch[n_height][n_r][n_c] = true;
                    queue.offer(new Point(current.cnt + 1, n_height, n_r, n_c));
                }
            }
        }
        return answer;
    }

    private static void init() {
        queue = new LinkedList<Point>();
        building = new char[L][R][C];
        ch = new boolean[L][R][C];
    }
}