[BaekJoon] 6593번 - 상범 빌딩 [Java][C++]

문제 링크

---

1. 아이디어

3차원 빌딩에서 목적지에 도달할 수 있는지, 도달할 수 있다면 몇 분이 걸리는지 구하는 문제로 3차원 탐색을 위한 육방 탐색을 활용한 BFS로 간단하게 해결할 수 있다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {

    static int[] dz = {0, 0, 0, 0, -1, 1};
    static int[] dr = {-1, 0, 1, 0, 0, 0};
    static int[] dc = {0, 1, 0, -1, 0, 0};
    static int h, n, m;
    static char[][][] grid;

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

        while (true) {
            st = new StringTokenizer(br.readLine());
            h = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            if (h == 0 && n == 0 && m == 0) break;

            grid = new char[h][n][m];
            int[] start = new int[3];
            int[] end = new int[3];

            for (int i = 0; i < h; i++) {
                for (int j = 0; j < n; j++) {
                    grid[i][j] = br.readLine().toCharArray();
                    for (int k = 0; k < m; k++) {
                        if (grid[i][j][k] == 'S') {
                            start = new int[]{i, j, k};
                        } else if (grid[i][j][k] == 'E') {
                            end = new int[]{i, j, k};
                        }
                    }
                }
                br.readLine();
            }

            int dist = bfs(start, end);
            if (dist == -1) {
                sb.append("Trapped!\n");
            } else {
                sb.append("Escaped in ").append(dist).append(" minute(s).\n");
            }
        }

        System.out.println(sb);
    }

    static int bfs(int[] start, int[] end) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(start);

        boolean[][][] vis = new boolean[h][n][m];
        vis[start[0]][start[1]][start[2]] = true;

        int dist = 0;

        while (!q.isEmpty()) {
            int sz = q.size();

            while (sz-- > 0) {
                int[] cur = q.poll();
                if (cur[0] == end[0] && cur[1] == end[1] && cur[2] == end[2]) return dist;

                for (int d = 0; d < 6; d++) {
                    int nz = cur[0] + dz[d];
                    int nr = cur[1] + dr[d];
                    int nc = cur[2] + dc[d];

                    if (nz < 0 || nz >= h || nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                    if (grid[nz][nr][nc] == '#' || vis[nz][nr][nc]) continue;

                    q.offer(new int[]{nz, nr, nc});
                    vis[nz][nr][nc] = true;
                }
            }

            dist++;
        }

        return -1;
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int dz[6] = {0, 0, 0, 0, -1, 1};
int dr[6] = {-1, 0, 1, 0, 0, 0};
int dc[6] = {0, 1, 0, -1, 0, 0};
int h, n, m;
char grid[31][31][31];
bool vis[31][31][31];

int bfs(auto s, auto e) {
    auto [sz, sr, sc] = s;
    auto [ez, er, ec] = e;

    queue<tuple<int, int, int>> q;
    q.push(s);

    vis[sz][sr][sc] = true;

    int dist = 0;

    while (!q.empty()) {
        int qsz = q.size();

        while (qsz--) {
            auto [z, r, c] = q.front();
            q.pop();

            if (z == ez && r == er && c == ec) return dist;

            for (int d = 0; d < 6; d++) {
                int nz = z + dz[d];
                int nr = r + dr[d];
                int nc = c + dc[d];

                if (nz < 0 || nz >= h || nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                if (grid[nz][nr][nc] == '#' || vis[nz][nr][nc]) continue;

                q.push({nz, nr, nc});
                vis[nz][nr][nc] = true;
            }
        }

        dist++;
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    while (true) {
        cin >> h >> n >> m;
        if (h == 0 && n == 0 && m == 0) break;

        memset(vis, 0, sizeof(vis));
        tuple<int, int, int> s, e;

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < n; j++) {
                cin >> grid[i][j];
                for (int k = 0; k < m; k++) {
                    if (grid[i][j][k] == 'S') {
                        s = {i, j, k};
                    } else if (grid[i][j][k] == 'E') {
                        e = {i, j, k};
                    }
                }
            }
        }

        int dist = bfs(s, e);
        if (dist == -1) {
            cout << "Trapped!\n";
        } else {
            cout << "Escaped in " << dist << " minute(s).\n";
        }
    }
}

---

3. 디버깅

없음.

---

4. 참고

없음.

---