[백준 6593번 / 상범 빌딩 / JAVA / BFS]

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

6593번: 상범 빌딩

 

문제 접근

 

이론상 맞는 거 같고 다른 분 풀이와 비교해도 내가 뭘 잘못한건지 못찾겠더라

시간을 너무 쏟는 거 같아서 일단 다른 분 풀이라도 올린다.

https://hanyeop.tistory.com/398

 

3차원인 거 빼면 다른 2차원 BFS와 크게 다르진 않다.

맵에 값을 넣고, bfs 메서드에서 반복문 돌면서 큐에 값이 있는지 체크하고 큐 값 꺼내와서 현재 위치에서 갈 수 있는 다음 공간 확인한 뒤 다시 큐에 값 넣어주는 작업을 반복하면서 출구를 찾으면 탈출 문구를 출력, 출구도 못찾았는데 더 이상 탐색할 공간이 없어서 큐에 값이 없게되면 탈출 불가 문구를 출력해준다.

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

class Point{
	int level;
	int row;
	int col;

	public Point(int level, int row, int col) {
		this.level = level;
		this.row = row;
		this.col = col;
	}
}

public class Main {
	static int l; // 층 수
	static int r; // 행 수
	static int c; // 열 수
	static int[][][] map;
	static int sl; // 시작 층
	static int sx; // 시작 행
	static int sy; // 시작 열
	static int count;
	static StringTokenizer st;
	static Queue<Point> q;

	// 동,서,남,북,상,하
	static int[] dl = {0,0,0,0,-1,1};
	static int[] dx = {0,0,1,-1,0,0};
	static int[] dy = {1,-1,0,0,0,0};

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

		while(true) { // l, r, c가 0이 되어야 끝나니 입력받기 위해 계속 돌아가야한다.
			st = new StringTokenizer(br.readLine());
			l = Integer.parseInt(st.nextToken());
			r = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			q = new LinkedList<Point>();
			count = 0;

			// 0,0,0 입력시 종료
			if(l == 0 && r == 0 && c == 0) {
				return;
			}

			map = new int[l][r][c];

			for(int i = 0; i < l; i++) {
				for(int j = 0; j < r; j++) {
					String str = br.readLine();
					for(int k = 0; k < c; k++) {
						char cur = str.charAt(k);

						if(cur == 'S') {
							map[i][j][k] = 2;
							sl = i;
							sx = j;
							sy = k;
						}
						else if(cur == '.') {
							map[i][j][k] = 0;
						}
						else if(cur == '#') {
							map[i][j][k] = 1;
						}
						else if(cur == 'E') {
							map[i][j][k] = 3;
						}
					}
				}
				br.readLine(); // 엔터를 눌러 층 사이 공간을 띄워줌
			}

			int result = solve();
			if(result == -1) {
				System.out.println("Trapped!");
			}
			else {
				System.out.println("Escaped in " + result + " minute(s).");
			}
		}
	}

	static int solve() {

		q.offer(new Point(sl,sx,sy));
		map[sl][sx][sy] = 100; // 방문 처리

		while(!q.isEmpty()) {

			count++;
			int size = q.size();

			// 큐의 깊이 만큼 반복하여 깊이 체크 (count) 
			for(int i = 0; i < size; i++) {
				Point cur = q.poll();

				for(int j = 0; j < 6; j++) {
					int cl = cur.level + dl[j];
					int cx = cur.row + dx[j];
					int cy = cur.col + dy[j];

					// 범위를 벗어나면
					if(cl < 0 || cl >= l || cx < 0 || cx >= r || cy < 0 || cy >= c) {
						continue;
					}

					// 출구에 도착하면
					if(map[cl][cx][cy] == 3) {
						return count;
					}

					// 방문한 곳이거나 벽이면
					if(map[cl][cx][cy] != 0) {
						continue;
					}

					map[cl][cx][cy] = 100; // 방문 처리
					q.offer(new Point(cl,cx,cy));
				}
			}
		}

		return -1;
	}
}