[ 백준 6593 ] 상범 빌딩 (C++)

백준의 상범빌딩(6593) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 기본적인 BFS인데, 일반적인 2차원 맵이 아닌 3차원 맵을 관리해줘야 하는 문제이다.

   가로, 세로, 높이가 있으니, 입력받는 맵도 3차원 배열에 입력받아야 하고, 방문체크를 하는 배열도 3차원 배열을

   사용해줘야 한다.

2) 1)번에서의 배열만 잘 사용한다면 어렵지 않은 문제이다. 일반 BFS와 같이, 갈 수 있으면서 탐색하지 않은 정점을

   탐색하되, 탐색방향이 상하좌우 4방향이 아닌, 상하좌우 위아래 총 6가지 방향에 대해서 탐색해 줘야 한다.

   어렵지 않은 문제이니 소스코드를 보면 쉽게 이해할 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 30
using namespace std;
 
int L, R, C;
char MAP[MAX][MAX][MAX];
bool Visit[MAX][MAX][MAX];
string Answer;
 
pair<pair<int, int>, int> Start, End;
 
int dx[] = { 0, 0, 1, -1, 0, 0 };
int dy[] = { 1, -1, 0, 0, 0, 0 };
int df[] = { 0, 0, 0, 0, 1, -1 };
 
void Initialize()
{
    memset(Visit, false, sizeof(Visit));
    Answer.clear();
}
 
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++)
        {
            for (int k = 0; k < C; k++)
            {
                cin >> MAP[i][j][k];
                if (MAP[i][j][k] == 'S')
                {
                    Start.first.first = i;
                    Start.first.second = j;
                    Start.second = k;
                }
                else if (MAP[i][j][k] == 'E')
                {
                    End.first.first = i;
                    End.first.second = j;
                    End.second = k;
                }
            }
        }
    }
}
 
int BFS(int a, int b, int c)
{
    queue<pair<pair<int, int>, pair<int, int>>> Q;
    Q.push(make_pair(make_pair(a, b), make_pair(c, 0)));    // 층, x, y, 이동횟수
    Visit[a][b][c] = true;
 
    while (Q.empty() == 0)
    {
        int f = Q.front().first.first;
        int x = Q.front().first.second;
        int y = Q.front().second.first;
        int Cnt = Q.front().second.second;
        Q.pop();
 
        if (f == End.first.first && x == End.first.second && y == End.second)
        {
            return Cnt;
        }
 
        for (int i = 0; i < 6; i++)
        {
            int nf = f + df[i];
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nf >= 0 && nx >= 0 && ny >= 0 && nf < L && nx < R && ny < C)
            {
                if (MAP[nf][nx][ny] == '#') continue;
                
                if (MAP[nf][nx][ny] == '.' || MAP[nf][nx][ny] == 'E')
                {
                    if (Visit[nf][nx][ny] == false)
                    {
                        Visit[nf][nx][ny] = true;
                        Q.push(make_pair(make_pair(nf, nx), make_pair(ny, Cnt + 1)));
                    }
                }
            }
        }
    }
    return -1;
}
 
void Solution()
{
    int R = BFS(Start.first.first, Start.first.second, Start.second);
    if (R == -1) cout << "Trapped!" << endl;
    else cout << "Escaped in " << R << " minute(s)." << endl;
}
 
void Solve()
{
    while (1)
    {
        Initialize();
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}