백준6593 - 상범 빌딩

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

6593번: 상범 빌딩

3차원 행렬을 이용한 다익스트라로 해결한 문제이다.

 

6개 방향으로 이동이 가능하며 #인 지점은 이동하지 못한다. 처음에 S의 위치를 큐에 삽입하여 시작점을 저장해둔다. for문을 이용하여 6개의 방향을 탐색하고 #인 지점과 S인 지점을 제외하고 모든 곳을 탐색한다. 탐색 도중 끝나는 지점인 E를 만난다면 그 지점의 탐색을 종료하고 다른 지점으로 넘어가 재탐색한다. 탐색을 진행하면서 현재 비용보다 갱신하려는 비용이 더 작으면 현재 비용을 갱신하려는 비용으로 갱신한다. 문제에서 각 층은 단 한개의 엔터만 입력이 들어온다면 그것으로 층 수를 구분한다. 

 

#include <iostream>
#include <queue>
#define MAX 51
#define INF 100000000
using namespace std;

//좌표 정보
class Point {
public:
	int x, y, z;
	Point(int x, int y, int z) {
		this->x = x; //층 수
		this->y = y; //세로
		this->z = z; //가로
	}
};

int L, R, C; //층으로 L, 세로로 R, 가로로 C
char mat[MAX][MAX][MAX]; //좌표 정보
int cost[MAX][MAX][MAX]; //비용

//상,하,좌,우,up,down
int dx[] = { 1,0,-1,0,0,0 };
int dy[] = { 0,1,0,-1,0,0 };
int dz[] = { 0,0,0,0,1,-1 };

int a, b, c; //E의 위치

queue<Point> q;

//초기에 다익스트라를 위하여 모든 공간의 비용을 INF로 초기화
void setting() {
	for (int i = 1; i < MAX; i++) {
		for (int j = 1; j < MAX; j++) {
			for (int k = 1; k < MAX; k++) {
				cost[i][j][k] = INF;
			}
		}
	}
}

void dijkstra() {
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int z = q.front().z;
		q.pop();

		if (mat[x][y][z] == 'E') { //도착 지점이면
			continue; //다른 지점에서 탐색
		}

		for (int i = 0; i < 6; i++) { //6방향
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nz = z + dz[i];

			if (1 <= nx && nx <= L && 1 <= ny && ny <= R && 1 <= nz && nz <= C && mat[nx][ny][nz] != '#' && mat[nx][ny][nz] != 'S') { //유효한 좌표 범위이고 벽이 아니고 출발지가 아니면
				if (cost[nx][ny][nz] > cost[x][y][z] + 1) { //현재 비용보다 갱신하려는 비용이 더 작으면
					cost[nx][ny][nz] = cost[x][y][z] + 1; //현재 비용을 갱신하려는 비용으로 갱신
					q.push(Point(nx, ny, nz)); //큐에 삽입
				}
			}
		}
	}
}

int main() {
	while (1) {
		cin >> L >> R >> C;
		
		if (L == 0) {
			break;
		}

		setting();

		for (int i = 1; i <= L; i++) {
			bool check = false; //엔터가 제일 처음에 들어왔는지 판단하는 변수
			for (int j = 1; j <= R; j++) {
				for (int k = 1; k <= C; k++) {
					cin >> mat[i][j][k];
					if (mat[i][j][k] == 'S') {
						q.push(Point(i, j, k));
						cost[i][j][k] = 0;
					}
					else if (mat[i][1][1] == '\n') { //엔터가 제일 처음에 들어오면
						check = true; //엔터가 제일 처음 들어왔다고 체크
						break; //탈출
					}
					else if (mat[i][j][k] == 'E') {
						a = i;
						b = j;
						c = k;
					}
				}
				if (check == true) { //엔터가 제일 처음에 들어왔다면
					break; //탈출
				}
			}
			if (check == true) { //엔터가 제일 처음에 들어왔다면
				i--; //층수를 한 층 내린다.
			}
		}
		
		dijkstra();

		if (cost[a][b][c] == INF) {
			cout << "Trapped!\n";
		}
		else {
			cout << "Escaped in " << cost[a][b][c] << " minute(s).\n";
		}
	}
}