[BaekJoon] 6593 상범 빌딩

1.  문제 링크

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

2.  문제

요약

• 상범 빌딩은 각 변의 길이가 1인 정육면체로 이루어져있고 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있습니다.
• 각 칸에서 인접한 6개의 칸(동, 서, 남, 북, 상, 하)로 1분의 시간을 들여 이동할 수 있습니다.
• 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있습니다.
• 상범 빌딩을 탈출하는데 걸리는 시간을 구하는 문제입니다.
• 입력: 입력은 여러 개의 테스트 케이스로 이루어지고, 각 테스트 케이스는 L, R, C로 시작합니다. L은 1 이상 30 이하의 정수인 상범 빌딩의 층 수이고, R은 1 이상 30 이하의 정수인 한 층의 행의 개수이며, C는 1 이상 30 이하의 정수인 한 층의 열의 개수입니다.
  다음 줄부터 C개의 문자로 이루어진 R개의 행이 L번 주어집니다. 각 문자는 상범 빌딩의 한 칸을 나타내고, 금으로 막혀있어 지나갈 수 없는 칸은 '#', 비어있는 칸은 '.'으로 표현됩니다. 시작 지점은 'S'로, 탈출할 수 있는 출구는 'E'로 표현됩니다.
  입력의 끝은 L, R, C 모두 0으로 표현됩니다.
  • 시작 지점과 출구는 항상 하나만 있습니다.
• 출력: 각 테스트 케이스마다 한 줄씩 답을 출력합니다.
  • 만약 탈출할 수 있다면 'Escaped in x minute(s).'를 출력합니다. 여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간입니다.
  • 만약 탈출할 수 없다면 'Trapped!'를 출력합니다.

3.  소스코드

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 StringBuilder sb = new StringBuilder();
	static char[][][] map;
	static boolean[][][] visited;
	static Point start, end;
	static int l, r, c;
	static int[] dx = {0, 0, 1, -1, 0, 0};
	static int[] dy = {1, -1, 0, 0, 0, 0};
	static int[] dz = {0, 0, 0, 0, 1, -1};
	
	static void input() {
		Reader scanner = new Reader();
		l = scanner.nextInt();
		r = scanner.nextInt();
		c = scanner.nextInt();
		while(true) {
			map = new char[l][r][c];
			visited = new boolean[l][r][c];
			if(l == 0 && r == 0 && c == 0) break;			
			for(int i = 0; i < l; i++) {
				for(int j = 0; j < r; j++) {
					String input = scanner.nextLine();
					for(int k = 0; k < c; k++) {
						map[i][j][k] = input.charAt(k);
						if(map[i][j][k] == 'S') {
							start = new Point(i, j, k);
						} else if(map[i][j][k] == 'E') {
							end = new Point(i, j, k);
						}
					}
				}
				scanner.nextLine();
			}
			bfs();
			l = scanner.nextInt();
			r = scanner.nextInt();
			c = scanner.nextInt();
		}
	}
	
	static void bfs() {
		Queue<Point> queue = new LinkedList<>();
		queue.offer(start);
		visited[start.page][start.row][start.column] = true;
		while(!queue.isEmpty()) {
			Point cur_position = queue.poll();
			if(map[cur_position.page][cur_position.row][cur_position.column] == 'E') {
				sb.append("Escaped in " + cur_position.time + " minute(s).\n");
				return;
			}
			for(int i = 0; i < 6; i++) {
				int cz = cur_position.page + dz[i];
				int cx = cur_position.row + dx[i];
				int cy = cur_position.column + dy[i];
				if(cz >= 0 && cz < l && cx >= 0 && cx < r && cy >= 0 && cy < c
						&& map[cur_position.page][cur_position.row][cur_position.column] != '#') {
					if(!visited[cz][cx][cy]) {
                        visited[cz][cx][cy] = true;
						queue.offer(new Point(cz, cx, cy, cur_position.time + 1));
					}
				}
			}
		}
		sb.append("Trapped!\n");
	}
	
	public static void main(String[] args) {
		input();
		System.out.println(sb.toString());
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			return str;
		}
	}
	
	static class Point {
		int page, row, column, time;
		public Point(int page, int row, int column) {
			this.page = page;
			this.row = row;
			this.column = column;
			this.time = 0;
		}
		public Point(int page, int row, int column, int time) {
			this.page = page;
			this.row = row;
			this.column = column;
			this.time = time;
		}
	}
}

4.  접근

• 해당 문제는 BFS를 이용하여 해결할 수 있습니다.
• 주어진 상범 빌딩의 정보를 3차원 배열 map에 담아주고 시작 지점과 출구는 각각 Point 타입 변수 start와 end에 넣어줍니다.
  • Point 타입은 층, 행, 열, 해당 위치까지 오는데 걸리는 시간을 나타내는 time 이 4가지를 멤버 변수로 갖습니다.
• BFS를 통해 탈출할 수 있는지 여부와 탈출할 수 있다면 어느 정도의 시간이 걸리는지를 구합니다.
  • BFS 탐색을 위한 Queue를 생성하고 시작 지점을 queue에 넣어줍니다.
  • BFS 탐색 시에 각 위치를 방문했는지를 나타내는 3차원 배열 visited를 생성하고 시작 지점은 방문되어있는 상태이기 때문에 해당 위치의 값을 true로 초기화합니다.
  • Queue가 비워지기 전까지 각 위치를 탐색하며 탈출 여부 및 시간을 구합니다.
    • Queue에서 현재 탐색할 위치를 뽑아 cur_position에 넣어줍니다.
      • cur_position의 동, 서, 남, 북, 상, 하 위치에 있는 곳들을 확인하면서 각 위치가 빌딩 내에 위치하고 금이 없어 이동할 수 있는 곳이며 아직 방문되지 않았다면 해당 위치를 이후에 탐색하기 위해 Queue에 넣어주고 해당 위치를 방문하였기 때문에 visited 값을 true로 변경합니다.
        • Queue에 넣어줄 때는 현재 탐색할 위치에서 한 번 이동하여 시간이 증가하였기 때문에 현재 탐색할 위치의 time 값에 1을 더한 시간을 갖도록 하여 객체를 생성한 후에 넣어줍니다.
      • 만약 현재 탐색할 위치가 출구라면 현재 탐색할 위치의 time 값을 x에 넣어 출력해주고 bfs() 함수를 끝냅니다.
  • Queue가 비워질 때까지 각 위치를 탐색한 후에도 아직 bfs() 함수가 종료되지 않았다면 출구에 도착하지 못한 것이므로 탈출할 수 없음을 출력합니다.