BaekJoon 6593 상범 빌딩

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

소스결과 1988 KB / 4 ms

출처 Baekjoon, University of Ulm Local Contest 1997 D

언어 C++ 17

분류 BFS, DFS, 다익스트라 알고리즘

 

설명

정육면체가 금! 으로 되어있는 상범 빌딩에서 시작지점과 탈출지점이 알려질 때 얼마나 빠르게 상범 빌딩에서 탈출 할 수 있는지 구하는 문제

 

각 변의 길이가 1인 단위 정육면체의 금! 으로 되어있는 상범빌딩에 갇혔다. 한 번에 움직일 때 1분이 걸린다.

구해야 하는 경우가 가장 빠른 탈출 시간을 요구한다. DFS로 해도 되고 BFS로 해도 된다. 굳이 다익스트라로 구하는 의미가 필요한가 싶긴 하다.

입력을 받을 때 각 문자 사이에 공백이 존재 하지 않기 떄문에 문자열로 입력 받아야 한다.

동시에 시작지점과 탈출구를 특정 변수에 저장해 주어야한다.

BFS/DFS의 구현에 있어서는 크게 신경 쓸 부분이 없다. 못가거나 몇번 갈 수 있다 라는 제한사항이 없고 다만 다르다면 3차원으로 풀어야 한다.

앞서 문제들을 여러 번 풀어 보았다면 어렵지 않은 문제다.

 

알고리즘

1. l r c를 입력받아 전부 0인지 판단하여 2번 루프를 진행한다.

2. 해당 턴의 문자 값들을 입력 받고 시작지점을 저장한다. 단, 시작지점 반복문 순서가 l r c 순서이기에 좌표를 저장할 때 유의하여야 한다.

3. 시작 지점을 기준으로 상, 하, 좌, 우, 위, 아래 6군데를 판단해 벽이 아니거나 방문하지 않았다면 다음 이동 지점을 방문한 것으로 처리하고 Push한다.

4. Queue가 비거나 현재 확인 하는 지점이 목적지와 같다면 루프를 종료한다.

5. 2 ~ 4 번에서 탈출 했는지 못했는지를 판단하여 각각 경우에 맞는 결과 값을 출력해준다.

 

소스코드

#include <iostream>
#include <queue>

using namespace std;

const int MAX = 30;

const short posX[6] = { 1, 0, -1, 0, 0, 0 };
const short posY[6] = { 0, 1, 0, -1, 0, 0 };
const short posZ[6] = { 0, 0, 0, 0, 1, -1 };

struct Point {
	short x;
	short y;
	short z;

	Point() : x(0), y(0), z(0) {};
	Point(short x, short y, short z) : x(x), y(y), z(z) {};
};

int main()
{
	int l, r, c;

	cin >> l >> r >> c;

	while (l && r && c)
	{
		bool isSuccess = false;
		int time = 0;
		char board[MAX][MAX][MAX + 1] = {};
		bool visited[MAX][MAX][MAX] = {};
		queue<Point> q;
		queue<Point> nextQ;
		Point start, des;

		for (int i = 0; i < l; i++)
			for (int j = 0; j < r; j++)
			{
				cin >> board[i][j];

				for (int k = 0; k < c; k++)
				{
					if (board[i][j][k] == 'S')
						start = Point(j, k, i);
					else if (board[i][j][k] == 'E')
						des = Point(j, k, i);
				}
			}

		q.push(start);
		visited[start.z][start.x][start.y] = true;

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

				if (cur.x == des.x && cur.y == des.y && cur.z == des.z)
				{
					isSuccess = true;
					break;
				}

				for (int i = 0; i < 6; i++)
				{
					short nextX = cur.x + posX[i];
					short nextY = cur.y + posY[i];
					short nextZ = cur.z + posZ[i];

					if (0 <= nextX && nextX < r && 0 <= nextY && nextY < c && 0 <= nextZ && nextZ < l && board[nextZ][nextX][nextY] != '#' && !visited[nextZ][nextX][nextY])
					{
						visited[nextZ][nextX][nextY] = true;
						nextQ.push(Point(nextX, nextY, nextZ));
					}
				}
			}

			if (isSuccess)
				break;

			while (!nextQ.empty())
			{
				q.push(nextQ.front());
				nextQ.pop();
			}

			time++;
		}

		if (isSuccess)
			cout << "Escaped in " << time << " minute(s).\n";
		else
			cout << "Trapped!\n";

		cin >> l >> r >> c;
	}
	
	return 0;
}