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

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

6593번: 상범 빌딩

 

크게 어려울만한 부분은 없는 BFS 문제이다.

좀 까다로운 부분이 있다면 3차원 배열을 써야 한다는 건데, 7569번 토마토를 풀었다면 풀 수 있다. (Tuple을 쓰면 좋다)

문자열 출력이라서 스펠링이나 띄어쓰기를 제대로 했는지 잘 봐야 하고(이것 때문에 3번 틀렸다;) 

모든 입력이 0일 때 까지 테스트 케이스가 반복해서 주어진다는 것, 따라서 큐를 비워야 한다는 것 정도 알고 있으면

문제 푸는데 좀 수월하다.

 

내가 생각한 방법은 다음과 같다.

1. 왼쪽,위쪽,아래쪽,오른쪽 / 상,하를 이동할 수 있으므로(상,하와 4방향 이동은 동시에 일어나지 않는다) 한 점을 꺼내고 상,하 두번 / 4방향 이동 네번을 수행한다.

2. 만약 범위를 벗어나지 않고 아직 방문하지 않은 정점이면 방문한다.

3. 이 과정을 큐가 모두 비거나 도착지점에 도착할때까지 반복한다.

4. 반복이 끝난 후 도착 지점의 값이 변경됐다면 도착한 것이므로 출력 양식에 맞게 그 값을 출력하고, 아니면 Trapped!를 출력한다.

 

#include <iostream>
#include <queue>
#include <tuple>
#include <string>
using namespace std;
#define MAX 32
#define WALL -1
#define SPACE 0
int l, r, c;
int dz[2] = { 1,-1 };
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int board[MAX][MAX][MAX];
tuple <int, int, int> finish;
queue <tuple<int, int, int>> q;
void input()
{

	char t;
	cin >> l >> r >> c;
	for (int i = 0; i < l; i++)
	{
		for (int j = 0; j < r; j++)
		{
			for (int k = 0; k < c; k++)
			{
				cin >> t;
				if (t == 'S')
				{
					board[i][j][k] = SPACE;
					q.push({ i,j,k });
				}
				else if (t == '.')
				{
					board[i][j][k] = SPACE;
				}
				else if (t == '#')
				{
					board[i][j][k] = WALL;
				}
				else if (t == 'E')
				{
					board[i][j][k] = SPACE;
					finish = { i,j,k };
				}
			}

		}
	}
}
string solve()
{
	int result = 0;
	while (!q.empty())
	{
		auto cur = q.front(); q.pop();
		if (board[get<0>(finish)][get<1>(finish)][get<2>(finish)])
			break;

		for (int i = 0; i < 2; i++)
		{
			int nz = get<0>(cur) + dz[i];
			int nx = get<1>(cur);
			int ny = get<2>(cur);
			if (nz < 0 || nz >= l || nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
			if (board[nz][nx][ny]) continue;
			board[nz][nx][ny] = board[get<0>(cur)][get<1>(cur)][get<2>(cur)] + 1;
			q.push({ nz,nx,ny });

		}
			for (int j = 0; j < 4; j++)
			{
				int nz = get<0>(cur);
				int nx = get<1>(cur) + dx[j];
				int ny = get<2>(cur) + dy[j];
				if (nz < 0 || nz >= l || nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
				if (board[nz][nx][ny]) continue;
				board[nz][nx][ny] = board[get<0>(cur)][get<1>(cur)][get<2>(cur)] + 1;
				q.push({ nz,nx,ny });
			}
	}

	result = board[get<0>(finish)][get<1>(finish)][get<2>(finish)];
	if (!result) return "Trapped!";
	else return "Escaped in " + to_string(result) + " minute(s).";
}
int main()
{
	cin.tie(0); ios::sync_with_stdio(0);
	while (true)
	{
		input();
		if (l == 0 && r == 0 && c == 0) return 0;
		cout << solve() << "\n";
		while (!q.empty()) q.pop();
	}
}