[BOJ] 6593번 상범빌딩 자바 문제풀이 (feat. BFS)

BFS 문제풀이

6593번 상범빌딩 문제는 시작점에서 종점까지 도달 가능한지와 도달했을 때 최소시간을 구하는 문제이다.
아래 문제 내용 중 문제 풀이에 도움되는 부분을 정리해 보았다.

6개의 칸(동, 서, 남, 북, 상, 하)으로 1분의 사간을 들여 이동할 수 있다. 
▶ dx, dy 테크닉을 이용한 동, 서, 남, 북에서 "상, 하"를 추가

시작 지점은 'S', 출구는 'E' & x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간
▶ 최단 시간 = BFS
▶ BFS를 이용해 방문 처리(visited) 및 최소 시간(timeTable) 배열을 초기화

참고 그림

 

 

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

public class Main {

    static boolean[][][] visited;
    static char[][][] map; // 입력값을 받아줄 3차원 char 배열
    static int[][][] timeTable; // 최소 시간을 담을 3차원 int 배열
    static Queue<int[]> queue = new LinkedList<>();
    
    // dx,dy 테크닉에서 상하를 추가
    static int[] dirRow = {0, 0, 1, 0, -1, 0};
    static int[] dirColumn = {0, 0, 0, -1, 0, 1};
    static int[] dirLaywer = {1, -1, 0, 0, 0, 0};
    
    static StringBuilder sb = new StringBuilder();


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true) {
            String inputString = br.readLine();

            StringTokenizer st = new StringTokenizer(inputString);
            int layer = Integer.parseInt(st.nextToken());
            int row = Integer.parseInt(st.nextToken());
            
            int column = Integer.parseInt(st.nextToken());

            if (layer == 0 && row == 0 && column == 0) {
                break;
            }

			// 입력받은 input 데이터 기반으로 각 배열 초기화
            visited = new boolean[layer][row][column];
            map = new char[layer][row][column];
            timeTable = new int[layer][row][column];

			// 시작 지점과 종점의 좌표를 담을 1차원 int 배열 선언
            int[] startPosition = new int[3];
            int[] endPosition = new int[3];

            for (int i = 0; i < layer; i++) {
                for (int j = 0; j < row + 1; j++) {
                    String inputRow = br.readLine();

                    if (!inputRow.isEmpty()) {
                        for (int k = 0; k < column; k++) {
                            map[i][j][k] = inputRow.charAt(k);
                            if (map[i][j][k] == 'S') {
                                startPosition = new int[]{i, j, k};
                            }

                            if (map[i][j][k] == 'E') {
                                endPosition = new int[]{i, j, k};
                            }
                        }
                    }
                }
            }

            bfs(startPosition, endPosition);
        }

        System.out.println(sb.toString());

    }

    static void bfs(int[] startPosition, int[] endPosition) {
        // 초기 데이터를 Queue에 담는다.
        queue.add(startPosition);

		// queue 가 빌때까지 반복
        while (!queue.isEmpty()) {
			
            // queue에서 값을 꺼내고
            int[] nowPosition = queue.poll();

			// 각 좌표 값을 int 타입으로 선언
            int nowLayer = nowPosition[0];
            int nowRow = nowPosition[1];
            int nowColumn = nowPosition[2];
			
            // queue 에서 꺼낸 좌표 값이 'E' 포지션이라면
            if (map[nowLayer][nowRow][nowColumn] == 'E') {
            	
                // timeTable 에서 해당 좌표의 값을 출력
                sb.append("Escaped in ").append(timeTable[nowLayer][nowRow][nowColumn]).append(" minute(s).\n");
                queue.clear();
                break;
            }

			// 상, 하를 추가했기에 6번 for 문 반복
            for (int i = 0; i < 6; i++) {
            
            	// 다음 좌표를 선언
                int nextLayer = nowLayer + dirLaywer[i];
                int nextRow = nowRow + dirRow[i];
                int nextColumn = nowColumn + dirColumn[i];
				
                // 다음좌표값이 0 < nextDimension < map.length 인지 검증
                if (boundaryCheck(nextLayer, nextRow, nextColumn)) {
                	
                    // 다음 좌표를 방문하지 않은 경우
                    if (!visited[nextLayer][nextRow][nextColumn]) {
						
                        // 'E' 와 '.' 만 골라서
                        if (map[nextLayer][nextRow][nextColumn] == '.' || map[nextLayer][nextRow][nextColumn] == 'E') {
							// 방문 처리
                            visited[nextLayer][nextRow][nextColumn] = true; 
                            // 다음 이동할 좌표를 queue에 담기
                            queue.add(new int[]{nextLayer, nextRow, nextColumn}); 
                            // timeTable에 시작점으로부터 최소 시간을 담아주기
                            timeTable[nextLayer][nextRow][nextColumn] = timeTable[nowLayer][nowRow][nowColumn] + 1;

                        }
                    }
                }
            }
        }
        
        // 만약 'E' 좌표의 최소 시간값이 0 인경우(시작점이 종점에 닿지못함) 예외처리
        if (timeTable[endPosition[0]][endPosition[1]][endPosition[2]] == 0) {
            sb.append("Trapped!").append("\n");
        }

    }

	// nextDimension 좌표 값 검증
    static boolean boundaryCheck(int nextLayer, int nextRow, int nextColumn) {

        if (nextLayer >= 0 && nextRow >= 0 && nextColumn >= 0) {
            if (nextLayer < map.length && nextRow < map[0].length && nextColumn < map[0][0].length) {
                return true;
            }
        }
        return false;
    }
}