상범빌딩


백준 6593: 상범빌딩

문제보기
Alt text

풀이

  • 3차원 배열
  • BFS 이용

소스코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static class Node {
		int h, r, c, cnt;

		Node(int h, int r, int c, int cnt) {
			this.h = h;
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}
	}

	static int[] dh = { 0, 0, 0, 0, 1, -1 };
	static int[] dr = { -1, 1, 0, 0, 0, 0 };
	static int[] dc = { 0, 0, -1, 1, 0, 0 };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int L = sc.nextInt(); // 빌딩의 층 수
			int R = sc.nextInt(); // 한 층의 행
			int C = sc.nextInt(); // 한 층의 열
			if(L==0 && R==0 && C==0)
				break;
			int[][][] map = new int[L][R][C];
			boolean[][][] visited = new boolean[L][R][C];
			Queue<Node> queue = new LinkedList<>();

			for (int i = 0; i < L; i++) {
				for (int j = 0; j < R; j++) {
					String str = sc.next();
					for (int k = 0; k < C; k++) {
						int ch = str.charAt(k);
						if (ch == 'S') {
							map[i][j][k] = -1;
							visited[i][j][k] = true;
							queue.add(new Node(i, j, k, 0));
						} else if (ch == '.')
							map[i][j][k] = 0;
						else if (ch == '#')
							map[i][j][k] = 1;
						else if (ch == 'E')
							map[i][j][k] = 99;
					}
				}
			}

			int min = Integer.MAX_VALUE;
			boolean flag = false;

			while (!queue.isEmpty()) {
				Node node = queue.poll();

				for (int d = 0; d < 6; d++) {
					int nh = node.h + dh[d];
					int nr = node.r + dr[d];
					int nc = node.c + dc[d];

					if (nh >= 0 && nr >= 0 && nc >= 0 && nh < L && nr < R && nc < C) {
						if (!visited[nh][nr][nc]) {
							if (map[nh][nr][nc] == 0) {
								visited[nh][nr][nc] = true;
								queue.add(new Node(nh, nr, nc, node.cnt + 1));
							} else if (map[nh][nr][nc] == 99) { // 출구에 도착
								min = Math.min(min, node.cnt + 1);
								flag = true;
							}
						}
					}
				}
			}

			if (flag)
				System.out.println("Escaped in " + min + " minute(s).");
			else
				System.out.println("Trapped!");
		}
	}
}