[Problem Solving] BOJ 6593: 상범 빌딩

문제 출처: https://www.acmicpc.net/problem/6593

 

출발지, 목적지, 장애물이 주어져있을때, 출발지에서 목적지까지 도달하는데 걸리는 최소비용을 구하는 문제이다.

 

2차원 -> 3차원으로 차원을 하나 더 늘리면된다. 2차원에서 진행하는것과 다를 게 없다.  

 

BFS를 수행하는 데, 핵심은 dist[next] > dist[cur] + 1이라면 dist[next] = dist[cur] + 1로 갱신하는 것이다.

 

BFS수행이 끝난 후 dist[end]가 무한대가 아니라면 Escaped In... 를 출력하고 무한대라면 Trapped!를 출력한다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
#include <set>
#define endl '\n'
using namespace std;

struct Point
{
    int x;
    int y;
    int z;
};

const int INF = 987654321;
int L, R, C;
int building[31][31][31];
bool visited[31][31][31];
int dist[31][31][31];
int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, 1, -1, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};
Point s, e;
string cr;

void input()
{
    cin >> L >> R >> C;
    if (L == 0 && R == 0 && C == 0)
    {
        exit(0);
    }
    for (int i = 0; i < L; i++)
    {
        for (int j = 0; j < R; j++)
        {
            string row;
            cin >> row;
            for (int k = 0; k < C; k++)
            {
                visited[i][j][k] = false;
                dist[i][j][k] = INF;
                if (row[k] == 'S')
                {
                    building[i][j][k] = 1;
                    dist[i][j][k] = 0;
                    s.z = i;
                    s.y = j;
                    s.x = k;
                }
                else if (row[k] == '.')
                {
                    building[i][j][k] = 1;
                }
                else if (row[k] == '#')
                {
                    building[i][j][k] = 0;
                }
                else if (row[k] == 'E')
                {
                    building[i][j][k] = 1;
                    e.z = i;
                    e.y = j;
                    e.x = k;
                }
            }
        }
        getline(cin, cr);
        getline(cin, cr);
    }
}

bool valid(int x, int y, int z)
{
    return (0 <= z && z < L && 0 <= y && y < R && 0 <= x && x < C);
}

void bfs(Point start)
{
    queue<Point> q;
    q.push(start);
    visited[start.z][start.y][start.x] = true;
    while (!q.empty())
    {
        Point cur_node = q.front();
        q.pop();
        int cur_z = cur_node.z;
        int cur_y = cur_node.y;
        int cur_x = cur_node.x;
        for (int i = 0; i < 6; i++)
        {
            int next_z = cur_z + dz[i];
            int next_y = cur_y + dy[i];
            int next_x = cur_x + dx[i];
            if (valid(next_x, next_y, next_z) && building[next_z][next_y][next_x] == 1 && !visited[next_z][next_y][next_x] && dist[next_z][next_y][next_x] > dist[cur_z][cur_y][cur_x] + 1)
            {
                dist[next_z][next_y][next_x] = dist[cur_z][cur_y][cur_x] + 1;
                Point next_node;
                next_node.z = next_z;
                next_node.y = next_y;
                next_node.x = next_x;
                q.push(next_node);
                visited[next_z][next_y][next_x] = true;
            }
        }
    }
}

void solution()
{
    bfs(s);
}

void output()
{
    if (dist[e.z][e.y][e.x] != INF)
    {
        cout << "Escaped in " << dist[e.z][e.y][e.x] << " minute(s)." << endl;
    }
    else
    {
        cout << "Trapped!" << endl;
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    while (1)
    {
        input();
        solution();
        output();
    }
    return 0;
}