[백준 / JAVA] 6593. 상범 빌딩

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

6593번: 상범 빌딩

 

---

💻 풀이 결과

💯 최종 코드

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 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;
	}
}

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

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

		while (true) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int L = Integer.parseInt(st.nextToken());
			int R = Integer.parseInt(st.nextToken());
			int C = Integer.parseInt(st.nextToken());

			// while문 종료
			if (L == 0) {
				break;
			}

			char[][][] building = new char[L][R][C];
			Queue<Node> queue = new LinkedList<>();
			boolean[][][] visited = new boolean[L][R][C];
			boolean isEscape = false;

			// 입력 받기
			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++) {
						building[i][j][k] = str.charAt(k);

						// 시작 지점
						if (building[i][j][k] == 'S') {
							queue.add(new Node(i, j, k, 0));
							visited[i][j][k] = true;
						}
					}
				}

				String tmp = br.readLine();
			}

			// BFS
			while (!queue.isEmpty()) {
				Node curr = queue.poll();

				// 탈출 출구
				if (building[curr.h][curr.r][curr.c] == 'E') {
					System.out.println("Escaped in " + curr.cnt + " minute(s)."); // 탈출 메세지
					queue.clear(); // 큐 비우기
					isEscape = true; // 탈출 성공 표시
					break;
				}

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

					// 기저 조건
					if (nh < 0 || nr < 0 || nc < 0 || nh >= L || nr >= R || nc >= C) { // 경계 검사
						continue;
					}
					if (visited[nh][nr][nc]) { // 방문 검사
						continue;
					}
					if (building[nh][nr][nc] == '#') { // 벽일 때
						continue;
					}

					queue.add(new Node(nh, nr, nc, curr.cnt + 1));
					visited[nh][nr][nc] = true;
				}
			} // BFS 끝

			if (!isEscape) {
				System.out.println("Trapped!");
			}
		} // 전체 while문 끝
	}
}

💬 풀이 과정

• 벽이 아닐 때(문자 '.')만 갈 수 있다고 생각했는데, 탈출구(문자 'E')도 우선 갈 수 있다고 생각하고 큐에 삽입을 해야 한다.
• 그래서 벽일 때(문자 '#')를 기저 조건으로 추가한다.
• 큐에 담을 노드의 구성요소에 cnt 도 포함해서 BFS 돌린다.

💡 깨달은 점

1. 3차원 배열

• 3차원 배열이 나와도 잘 다룰 수 있다.

2. 기저 조건 설정

• 기저 조건을 잘 설정해야 한다.
• BFS를 갈 수 있을 때와 가지 못할 때를 잘 구분해야 한다.