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

 

1. 제목

- 백준 6593 상범 빌딩

- BOJ 6593 상범 빌딩

문제 링크 : 6593번: 상범 빌딩 (acmicpc.net)

6593번: 상범 빌딩

 

---

2. 문제 설명

상범 빌딩 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	13836	5015	3929	36.096%

문제

 

당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다.

당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까?

입력

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.

그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다. 시작 지점과 출구는 항상 하나만 있다.

출력

각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 다음과 같이 출력한다.

Escaped in x minute(s).

여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다.

만일 탈출이 불가능하다면, 다음과 같이 출력한다.

Trapped!

예제 입력 1 복사

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

예제 출력 1 복사

Escaped in 11 minute(s).
Trapped!

출처

Contest > University of Ulm Local Contest > University of Ulm Local Contest 1997 D번

• 문제의 오타를 찾은 사람: hwajin, madcatlove
• 데이터를 추가한 사람: speedlin1964
• 문제를 번역한 사람: yh0413

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

3. 풀이 과정

3차원 문제라 방향 벡터를 기존에 상하좌우에서 위층, 아래층까지 추가 해줘야 하는 문제였어요.
bfs 탐색을 사용하면 시작 지점부터 각 위치까지 도달할 수 있는 시간을 맵에 표현할 수 가 있는데 이 방법을 사용하기 위해서 맵을 문자가 아닌 숫자로 구현했어요.

.(빈공간)        => 0

#(벽)              => 1

E(탈출지점)   => 2

S(시작지점)   => 3

빈공간, 벽, 탈출지점을 표현하느라 시작 지점이 3부터 시작하게 되는데 이러면 맵이 이런 식으로 구현이 돼요.

맵이 구현이 되었다면 0인 지점만 탐색하게 진행하고 2인 지점을 찾게 되면 탈출할 수 있는 것이므로 2인 지점을 찾은 바로 전 지점에서 시간이 1 늘어 날 것이고 처음에 맵을 표현하느라 3부터 시작 했기 때문에 출발지에서 각 지점까지 도착하는데 걸리는 시간은 해당 지점 값 - 3이 되게 될 텐데 제 코드에서는 마지막 도착지는 방문처리를 하지 않고 찾기만 했을 때 바로 시간을 반환시킬 것이기 때문에 -2를 해주면 정답이 돼요.

 

---

4. 함수 설명

Reset : 테스트 케이스가 여러 개 일 수가 있는데 이때 이전에 있던 데이터들이 남아 있으면 새로운 테스트가 정상적으로 작동하지 않기 때문에 맵과 큐를 비워주는 함수예요.

---

5. 코드

#define MAX 30 + 1

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct pos
{
	int l, r, c;
};

// 상하좌우 위층, 아래층
int dx[6] = { 0, 0,-1, 1 , 0, 0};
int dy[6] = { 1, -1, 0, 0, 0, 0};
int dl[6] = { 0, 0, 0, 0, 1, -1};

int map[MAX][MAX][MAX];
int L, R, C;

queue <pos> q;

int Bfs()
{
	while (!q.empty())
	{
		pos cur = q.front();
		q.pop();

		// 상하좌우 위층, 아래층
		for (int dir = 0; dir < 6; dir++)
		{
			int nc = cur.c + dx[dir];
			int nr = cur.r + dy[dir];
			int nl = cur.l + dl[dir];

			if (nr < 0 || nc < 0 ||  nl < 0 || nr >= R || nc >= C  || nl >= L)
				continue;
			if (map[nl][nr][nc] == 2)
				return map[cur.l][cur.r][cur.c];
			
			if (map[nl][nr][nc] != 0)
				continue;

			map[nl][nr][nc] = map[cur.l][cur.r][cur.c] + 1;
			q.push({ nl, nr, nc });
		}

	}
	return -1;	
}

void Reset()
{
	for (int l = 0; l < L; l++)
	{
		for (int r = 0; r < R; r++)
		{
			for (int c = 0; c < C; c++)
			{
				map[l][r][c] = '.';
			}
		}
	}
	while (!q.empty())
		q.pop();
}

int main()
{
	// #벽, . 빈칸, S 시작 지점, E 출구
	while(true)
	{
		cin >> L >> R >> C;
		if (L == 0)
			break;

		for (int l = 0; l < L; l++)
		{
			for (int r = 0; r < R; r++)
			{
				for (int c = 0; c < C; c++)
				{
					char ch;
					cin >> ch;

				    if (ch == '.')
					map[l][r][c] = 0;
					else if (ch == '#')
						map[l][r][c] = 1;
					else if (ch == 'E')
						map[l][r][c] = 2;
					else if(ch == 'S')
					{
						map[l][r][c] = 3;
						q.push({ l, r, c });
					}				

				}
			}
		}

		int time = Bfs();
		if (time == -1)
			cout << "Trapped!" << endl;
		else
			cout << "Escaped in " <<  time - 2 << " minute(s)." << endl;

		Reset();		
	}
	return 0;
}