백준 6593번 상범 빌딩

문제

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

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

문제풀이

사용한 알고리즘 : BFS

(1) 코드 10~11

 string 2차 배열로 건물정보를 받았습니다.
 ' arr[x][y][z] : z층, x행, y열 ' 로 설정하였습니다.

(2) 코드 7~8

 이동 방향 6 개에 대한 배열입니다.
 순서대로 ' 위row, 아래row, 왼쪽column, 오른쪽column, 위층, 아래층' 이동입니다.

(3) 코드 14~40

 BFS 를 구현하는 함수입니다.
 queue에는 tuple<층, row, column, 걸린시간 > 이 들어갑니다.
 매 탐색시, 코드 (2)의 6가지 방향 중 이동 가능한 곳을 찾습니다.

	#include <bits/stdc++.h>
	using namespace std;
	// < z, x, y , time >
	typedef tuple<int, int, int, int> tp;
	int L, R, C;
	int dx[] = { -1,1,0,0,0,0 };
	int dy[] = { 0,0,-1,1,0,0 };
	int dz[] = { 0,0,0,0,-1,1 };
	// arr[z][x][y] : 층(z), 행(x), 열(y)
	string arr[33][33];
	bool visited[33][33][33];
	void CanOut(int a, int b, int c) {
	queue<tp> Q;
	visited[a][b][c] = true;
	Q.push(tp(a, b, c, 0));
	while (!Q.empty()) {
	tp now = Q.front();
	Q.pop();
	int z = get<0>(now);
	int x = get<1>(now);
	int y = get<2>(now);
	int t = get<3>(now);
	if (arr[z][x][y] == 'E') {
	cout << "Escaped in " << t << " minute(s)." << '\n';
	return;
	}
	for (int i = 0; i < 6; ++i) {
	int nz = z + dz[i];
	int nx = x + dx[i];
	int ny = y + dy[i];
	if (nz < 0 || nz >= L || nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
	if (visited[nz][nx][ny] || arr[nz][nx][ny] == '#') continue;
	Q.push(tp(nz, nx, ny, t + 1));
	visited[nz][nx][ny] = true;
	}
	}
	cout << "Trapped!" << '\n';
	}
	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	while (cin >> L >> R >> C) {
	//초기화
	for (int i = 0; i < 30; ++i)
	for (int j = 0; j < 30; ++j)
	arr[i][j].clear();
	memset(visited, false, sizeof(visited));
	for (int z = 0; z < L; ++z)
	for (int x = 0; x < R; ++x)
	cin >> arr[z][x];
	for (int z = 0; z < L; ++z)
	for (int x = 0; x < R; ++x)
	for (int y = 0; y < C; ++y)
	if (arr[z][x][y] == 'S')
	CanOut(z, x, y);
	}
	return 0;
	}

view raw BOJ 10597.cpp hosted with ❤ by GitHub