(백준) (Java) 6593 – 상범빌딩

(프로그래머) (코틀린) –

(코드포스) (코틀린) –

문제 정보

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

6593호 : 상범빌딩

당신은 상범빌딩에 갇혔습니다. 여기서 나가는 가장 빠른 방법은 무엇입니까? 상범 건물은 한 변의 길이가 1인 정육면체(단위 정육면체)로 구성되어 있습니다. 각 큐브는 금으로 만들어집니다.

www.acmicpc.net

난이도: G5

유형: BFS

---

문제를 해결하다

상, 하, 동, 서, 남, 북의 6방향으로 이동할 수 있는 3차원 BFS 문제

표준 BFS 솔루션에서 z축만 확장하면 쉽게 풀 수 있는 문제입니다.

아래 코드를 수정하면 출구에 도달했을 때 다시 대기하지 않고 즉시 검색을 중지합니다.

---

암호

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 {

    private final int()() dir = {{0, 1, 0}, {0, -1, 0}, {1, 0, 0}, {-1, 0, 0}, {0, 0, -1}, {0, 0, 1}};
    private int L, R, C;
    private char()()() building;
    private boolean()()() isVisited;
    private int res;

    public void bfs(int startL, int startR, int startC, int cnt) {
        Queue<Integer> que = new LinkedList<>();
        que.add(startL);
        que.add(startR);
        que.add(startC);
        que.add(cnt);
        isVisited = new boolean(L)(R)(C);
        isVisited(startL)(startR)(startC) = true;

        while (!que.isEmpty()) {
            int curZ = que.poll();
            int curX = que.poll();
            int curY = que.poll();
            int curCnt = que.poll();

            if (building(curZ)(curX)(curY) == 'E') {
                res = curCnt;
                break;
            }

            for (int k = 0; k < 6; k++) {
                int nX = curX + dir(k)(0);
                int nY = curY + dir(k)(1);
                int nZ = curZ + dir(k)(2);

                if (nX < 0 || nX >= R || nY < 0 || nY >= C || nZ < 0 || nZ >= L) {
                    continue;
                }
                if (isVisited(nZ)(nX)(nY)) {
                    continue;
                }
                if (building(nZ)(nX)(nY) == '#') {
                    continue;
                }

                que.add(nZ);
                que.add(nX);
                que.add(nY);
                que.add(curCnt + 1);
                isVisited(nZ)(nX)(nY) = true;
            }
        }
    }

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        while (true) {
            st = new StringTokenizer(br.readLine());
            L = Integer.parseInt(st.nextToken());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
            if (L == 0 && R == 0 && C == 0) {
                break;
            }

            int startL = 0;
            int startR = 0;
            int startC = 0;
            building = new char(L)(R)(C);
            for (int i = 0; i < L; i++) {
                for (int j = 0; j < R; j++) {
                    String input = br.readLine();
                    for (int k = 0; k < C; k++) {
                        building(i)(j)(k) = input.charAt(k);
                        if (building(i)(j)(k) == 'S') {
                            startL = i;
                            startR = j;
                            startC = k;
                        }
                    }
                }
                br.readLine();
            }

            res = -1;
            bfs(startL, startR, startC, 0);

            if (res == -1) {
                sb.append("Trapped!");
            } else {
                sb.append("Escaped in ").append(res).append(" minute(s).");
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String() args) throws IOException {
        new Main().solution();
    }
}