[BOJ] 백준 6593번 상범 빌딩 C++

문제

https://www.acmicpc.net/problem/6593

6593번: 상범 빌딩

풀이

BFS로 해결할 수 있었다. 

이 문제 같은 경우 단순 동, 서, 남, 북만 탐색하는 것이 아니라 빌딩의 높이에 따른 동, 서, 남, 북, 상, 하까지 탐색해야하기 때문에 dx, dy, dz라는 3개의 배열을 만들어주었다.

이외에도 우리가 탐색해야할 건물이나 거리 배열 등도 3차원으로 만들어주기만 하면 일반적인 BFS 문제들과 크게 다른 것은 없다.

Queue에는 x, y, z 좌표인 3개의 자료형을 담기위해 tuple을 사용하여 시작 좌표를 Queue에 넣어주었고 필자는 문자보단 숫자로 BFS를 구현하는 것이 편했기에 입력 받는 문자들을 숫자로 치환해주었다.

갈 수 있는 곳 - 1, 갈 수 없는 곳 - 0, 출구 - 7로 관리해주어 탐색을 하다 빌딩의 원소가 7인 곳(출구)를 만나면 탐색을 중지하고 해당 좌표까지의 거리를 리턴해주었다. Queue가 비었는데 아직 리턴을하지 못했다면 BFS로 출구까지 도달할 수 없는 그래프이므로 "Trapped!"를 출력해주면 된다. 

코드

+#include<iostream>
#include<queue>
#include<tuple>

using namespace std;

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

void bfs(int board[31][31][31], int dist[31][31][31], int startX, int startY, int startZ, int l, int n, int m)
{
	// BFS
	queue<tuple<int, int, int>> q;
	q.push({ startX, startY, startZ });
	dist[startX][startY][startZ] = 0;


	while (!q.empty())
	{
		auto cur = q.front();
		q.pop();

		for (int dir = 0; dir < 6; dir++)
		{
			int nx = get<0>(cur) + dx[dir];
			int ny = get<1>(cur) + dy[dir];
			int nz = get<2>(cur) + dz[dir];

			if (nx < 0 || nx > n || ny < 0 || ny > m || nz < 0 || nz > l)
			{
				continue;
			}
			if (dist[nx][ny][nz] >= 0 || board[nx][ny][nz] == 0)
			{
				continue;
			}

			q.push({ nx, ny, nz });
			dist[nx][ny][nz] = dist[get<0>(cur)][get<1>(cur)][get<2>(cur)] + 1;

			if (board[nx][ny][nz] == 7)
			{
				cout << "Escaped in " << dist[nx][ny][nz] << " minute(s)." << "\n";
				return;
			}
		}
	}

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

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

	while (true)
	{
		int l, n, m;
		int startX = 0;
		int startY = 0;
		int startZ = 0;
		int board[31][31][31];
		int dist[31][31][31];

		cin >> l >> n >> m;

		if (l == 0 && n == 0 && m == 0)
		{
			break;
		}

		for (int k = 0; k < l; k++)
		{
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < m; j++)
				{
					char c;
					cin >> c;
					if (c == '.')
					{
						board[i][j][k] = 1;
					}
					else if (c == '#')
					{
						board[i][j][k] = 0;
					}
					else if (c == 'S')
					{
						board[i][j][k] = 0;
						startX = i;
						startY = j;
						startZ = k;
					}
					else if (c == 'E')
					{
						board[i][j][k] = 7;
					}
					dist[i][j][k] = -1;
				}
			}
		}

		bfs(board, dist, startX, startY, startZ, l, n, m);
	}
}