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

#6593 상범 빌딩

난이도 : 골드 5

유형 : 그래프 / BFS 

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 탐색 문제이다. 한가지 특징이 있다면 3차원 맵을 탐색해야 한다는 점이다. 탐색 방향은 총 6가지 상, 하, 좌, 우, 위, 아래로 탐색해주면 된다.

 

3차원 배열 탈출하기

설계

1. 'S'인 시작점 좌표를 저장한다 (sx, sy, sz)
2. (sx, sy, sz)를 시작으로 bfs 탐색을 한다.
   1. 'E'지점에 도착하면 탐색을 종료하고 이동한 최단 거리를 출력해준다. "Escaped in x minute(s)."
   2. 모든 탐색이 끝나도 'E'지점에 도착하지 못하였다면 "Trapped!" 를 출력한다.

 

풀이 코드 

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 int l,r,c;
	static char[][][] map;
	static StringBuilder sb = new StringBuilder();
	static int[] dx= {-1,1,0,0,0,0};
	static int[] dy = {0,0,-1,1,0,0};
	static int[] dz = {0,0,0,0,1,-1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		while(true) {
			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) {
				System.out.println(sb.toString());
				return;
			}
			
			int sx=0,sy=0,sz=0;
			map =new char[l][r][c];
			for(int i=0; i<l; i++) {
				for(int j=0; j<r; j++) {
					String line = br.readLine();
					for(int k=0; k<c; k++) {
						map[i][j][k] = line.charAt(k);
						if(map[i][j][k] == 'S') {
							sx =k; sy = j; sz =i;
							map[i][j][k] = '.';
						}
					}
				}
				br.readLine();
			}
			bfs(sx, sy, sz);
		}
	}
	
	static void bfs(int x, int y, int z) {
		Queue<int[]> q = new LinkedList<>();
		boolean[][][] check = new boolean[l][r][c];
		q.add(new int[] {x,y,z,0});
		check[z][y][x] = true;
		
		while(!q.isEmpty()) {
			int[] p = q.poll();
			int px=p[0], py=p[1], pz=p[2];
			int move = p[3];
			
			if(map[pz][py][px]=='E') {
				sb.append("Escaped in " + move+" minute(s).\n");
				return;
			}
			
			for(int d=0; d<6; d++) {
				int nx = px + dx[d], ny = py + dy[d], nz = pz + dz[d];
				if(nx <0 || ny <0 || nz<0 || nx>c-1 || ny>r-1 || nz >l-1) continue;
				if(check[nz][ny][nx]) continue;
				if(map[nz][ny][nx]=='.' || map[nz][ny][nx]=='E') {
					check[nz][ny][nx] = true;
					q.add(new int[] {nx, ny, nz, move+1});
				}
			}
		}
		sb.append("Trapped!\n");
	}
}