[백준 6593] 상범 빌딩 (자바)

백준 6593번 상범 빌딩 (자바)

 

 

 

출처

www.acmicpc.net/problem/6593

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!

 

 

 

입출력 예

입출력 예 1

 

 

접근 방법

이전에 풀었던 3차원 토마토 문제와 유사하다.

처음에는 배열에 값 입력 시에 시작 위치를 찾았을 때 큐에 넣어서 BFS연산을 시작하려 했지만 오류가 나서 계속 틀렸다.

이후에 전역선언한 큐를 bfs문 안에 지역 선언했더니 문제없이 돌아갔다.

이것이 왜 해결됐는지는 잘 모르겠다.. 향후 꼭 해결이유를 찾고 싶다.

 

1. 최단 길이를 구해야 하므로 bfs를 사용하자.

 

2. 0, 0, 0을 입력시에 종료돼야 하니 while문을 사용하자.

 

3. 시작 위치와 끝 위치의 변수를 각각 생성해서 저장한다. 

시작 위치는 bfs연산에 매개변수로 보낼 것이기 때문에 지역변수, 끝 위치는 맨 나중에 비교하기 위해 전역 변수로 선언한다.

 

4. bfs로 연산하며 현재 위치 시간의 +1 하여 인접행렬에 넣어준다.

 

5. 전역변수로 선언한 끝 위치를 만나면 경과한 초를 list에 넣어주고 return 한다.

 

6. 만약 끝 위치를 만나지 못한다면 Trapped를 list에 넣어준다.

 

7. list를 출력한다.

 

 

 

 

내 코드

package dfsbfs;

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

public class SangBumBuilding {
	
	/**
	 * 백준 6593 상범빌딩 (https://www.acmicpc.net/problem/6593)
	 */
	
	private static int l, r, c;
	private static char[][][] map;
	private static int[][][] time;
	private static boolean[][][] visit;
	private static boolean flag = false;
	
	//상하앞뒤우좌
	private static int[] dz = {-1, 0, 0, 1, 0, 0};
	private static int[] dy = {0, -1, 1, 0, 0, 0};
	private static int[] dx = {0, 0, 0, 0, -1, 1};
	
	private static int endZ = 0;
	private static int endY = 0;
	private static int endX = 0;
	
	private static ArrayList<String> list = new ArrayList<String>();
	
	public static void main(String[] args) throws IOException {
		
		//정육면체
		//대각선X
		//S : 시작
		
		//# : 못지나감
		//. : 비어있음
		
		//E : 출구
		
		//최단시간 : bfs!
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		while (true) {
			flag = false;
			StringTokenizer st = new StringTokenizer(reader.readLine());
			
			if(!st.hasMoreTokens())
                st = new StringTokenizer(reader.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];
			time = new int[l][r][c];
			visit = new boolean[l][r][c];
			
			int startZ = 0;
			int startY = 0;
			int startX = 0;
			
			for (int i=0; i<l; i++) {
				for (int j=0; j<r; j++) {
					String input = reader.readLine();
					
					if(input.equals("")) 
                        input = reader.readLine();
					
					for (int k=0; k<c; k++) {
						map[i][j][k] = input.charAt(k);
						
						if (map[i][j][k] == 'S') {
							startZ = i;
							startY = j;
							startX = k;
						} else if (map[i][j][k] == 'E') {
							endZ = i;
							endY = j;
							endX = k;
						} 
						
					}
				}
			}
			
			bfs(startZ, startY, startX);
			
			if (!flag) {
				list.add("Trapped!");
			}
		}
		
		for (String st : list) {
			System.out.println(st);
		}
		
	}


	private static void bfs(int startZ, int startY, int startX) {
		
		Queue<Building> q = new LinkedList();
		q.add(new Building(startZ, startY, startX));
		visit[startZ][startY][startX] = true;
		
		while (!q.isEmpty()) {
			
			Building bd = q.remove();
			int qz = bd.l;
			int qy = bd.r;
			int qx = bd.c;
			
			if (qz == endZ && qy == endY && qx == endX) {
				//E만나면 종료
				list.add("Escaped in " + time[qz][qy][qx] + " minute(s).");
				flag = true;
				return;
			}
			
			for (int i=0; i<dx.length; i++) {
				int nz = qz + dz[i];
				int ny = qy + dy[i];
				int nx = qx + dx[i];
				
				if (nz < 0 || ny < 0 || nx < 0 || nz >= l || ny >= r || nx >= c) {
					continue;
				}
				
				if (map[nz][ny][nx] != '#' && !visit[nz][ny][nx]) {
					// 방문x, ., 시간 -1(미방문)
					visit[nz][ny][nx] = true;
					time[nz][ny][nx] = time[qz][qy][qx] + 1;
					q.add(new Building(nz, ny, nx));
				}
				
			}
		}
		
		
	}
}


class Building {
	int l, r, c;
	Building(int l, int r, int c) {
		this.l = l;
		this.r = r;
		this.c = c;
	}
}

 

 

 

고려할 점

1. 큐를 지역변수로 사용할 것

2. 시작과 끝 위치를 활용할 것

3. 최단시간이니 bfs 사용할 것!