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

문제 링크

---

1. 문제 풀이

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

---

2. 코드

1. 풀이 [Java]

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

public class Main {

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

    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());
            int L = Integer.parseInt(st.nextToken());
            int R = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            if (L == 0 && R == 0 && C == 0) break;

            char[][][] building = new char[L][R][C];
            int[] start = new int[3];
            int[] end = new int[3];
            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') {
                            start = new int[]{i, j, k};
                        } else if (building[i][j][k] == 'E') {
                            end = new int[]{i, j, k};
                        }
                    }
                }
                br.readLine();
            }

            int dist = bfs(start, end, L, R, C, building);
            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, int L, int R, int C, char[][][] building) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(start);

        boolean[][][] visited = new boolean[L][R][C];
        visited[start[0]][start[1]][start[2]] = true;

        int dist = 0;

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

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

                for (int d = 0; d < 6; d++) {
                    int nh = node[0] + dh[d];
                    int nr = node[1] + dr[d];
                    int nc = node[2] + dc[d];

                    if (nh < 0 || nh >= L || nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                    if (building[nh][nr][nc] == '#' || visited[nh][nr][nc]) continue;

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

            dist++;
        }

        return -1;
    }
}

2. 풀이 [C++]

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

int dh[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};

char building[30][30][30];
bool visited[30][30][30];

struct Node {
    int h, r, c;
};

int bfs(const Node& s, const Node& e, int L, int R, int C) {
    queue<Node> q;
    q.push(s);

    visited[s.h][s.r][s.c] = true;

    int dist = 0;

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

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

            if (h == e.h && r == e.r && c == e.c) return dist;

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

                if (nh < 0 || nh >= L || nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                if (building[nh][nr][nc] == '#' || visited[nh][nr][nc]) continue;

                q.push({nh, nr, nc});
                visited[nh][nr][nc] = true;
            }
        }

        dist++;
    }

    return -1;
}

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

    while (true) {
        int l, r, c;
        cin >> l >> r >> c;

        if (l == 0 && r == 0 && c == 0) break;

        memset(building, 0, sizeof(building));
        memset(visited, 0, sizeof(visited));
        Node s, e;
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < r; j++) {
                string input;
                cin >> input;

                for (int k = 0; k < c; k++) {
                    building[i][j][k] = input[k];

                    if (building[i][j][k] == 'S') {
                        s = {i, j, k};
                    } else if (building[i][j][k] == 'E') {
                        e = {i, j, k};
                    }
                }
            }
        }

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

---