[백준 6593] 상범 빌딩

문제 풀이

 

3차원에서 상범이가 탈출할 수 있으면 최단 경로를 리턴하고, 탈출할 수 없다면 Trapped!라고 출력하면 된다.

 

기존에는 2차원 배열에서 상,하,좌,우만 구현했다면 이번에는 위층과 아래층을 갈 수 있도록 만들어야 한다.

const int dx[] = { 0,0,-1,1,0,0 };
const int dy[] = { 1,-1,0,0,0,0 };
const int dz[] = { 0,0,0,0,-1,1 };

따라서 6방향으로 나눠서 구현해준다.

 

기존 BFS 코드를 3차원으로 구현해주기만 하면 문제를 해결할 수 있다.

주의할 점은 다른 칸으로 이동할 때 방문체크랑 '#'이 아닌 곳으로 가야 하면서 동시에 몇 번만에 그 위치에 왔는지 기록을 해야 한다.

 

아래의 구현은 i = Z, j = X(행), k = Y(열)로 구현했다.

소스 코드

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <tuple>
using namespace std;

const int MAX = 31;
const int dx[] = { 0,0,-1,1,0,0 };
const int dy[] = { 1,-1,0,0,0,0 };
const int dz[] = { 0,0,0,0,-1,1 };

int L, R, C;
char board[MAX][MAX][MAX];
bool visit[MAX][MAX][MAX];

tuple<int, int, int> first, last; // (z,x,y)

struct Info
{
	int z;
	int x;
	int y;
	int cnt;
};

void bfs()
{
	fill(visit[0][0], visit[0][0] + MAX * MAX * MAX, false);
	queue<Info> q;
	
	q.push({ get<0>(first), get<1>(first), get<2>(first), 0 });
	visit[get<0>(first)][get<1>(first)][get<2>(first)] = true;
	while (!q.empty())
	{
		int z = q.front().z;
		int x = q.front().x;
		int y = q.front().y;
		int cnt = q.front().cnt;
		q.pop();

		if (x == get<1>(last) && y == get<2>(last) && z == get<0>(last))
		{
			cout << "Escaped in " << cnt << " minute(s).\n";
			return;
		}

		for (int i = 0; i < 6; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nz = z + dz[i];
			if (nx < 0 || ny < 0 || nz < 0 || nx >= R || ny >= C || nz >= L) continue;
			if (board[nz][nx][ny] != '#' && visit[nz][nx][ny] == false)
			{
				visit[nz][nx][ny] = true;
				q.push({ nz,nx,ny,cnt + 1 });
			}
		}
	}

	cout << "Trapped!\n";
	return;
}

void input()
{
	for (int i = 0; i < L; i++)
	{
		for (int j = 0; j < R; j++)
		{
			for (int k = 0; k < C; k++)
			{
				cin >> board[i][j][k];
				if (board[i][j][k] == 'S')
					first = { i,j,k };
				else if (board[i][j][k] == 'E')
					last = { i,j,k };
			}
		}
	}
}

void solve()
{
	while (true)
	{
		cin >> L >> R >> C;
		if (L == 0 && R == 0 && C == 0) break;
		input();
		bfs();
	}

}

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

	solve();
	return 0;
}