백준 6593: 상범 빌딩

문제 요약

3차원 배열의 빌딩에서 시작지점과 탈출지점이 주어지면, 탈출할 수 있는 최소의 시간을 출력하시오.
탈출이 불가능하다면 "Trapped!"를 출력하시오.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS

문제 풀이

BFS로 풀면 된다. S를 스타트 지점으로 잡고, 동서남북상하로 E에 닿을때까지 BFS하면 된다.

메모리 초과와 시간 초과를 주의하자. string에 cin으로 입력받고, tuple<>을 사용하였더니 시간 초과가 나서 tuple<>은 pair<>로 바꾸고, 입력도 char[]로 바꾸었다.

또 왜인지 모르게 메모리 초과도 나오길래 가능한 부분은 int가 아닌 short를 써주었다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <memory.h>

using namespace std;

bool visited[30][30][30];
char ary[30][30][30];

int main()
{
	int l, r, c;
	short res;
	bool sol, s;
	queue<pair<short,pair<short,short>>> q;

	while (true) {
		scanf("%d%d%d", &l, &r, &c);
		if (l == (r == (c == 0))) break;

		memset(&visited[0][0][0], false, l * r * c);
		q = queue<pair<short, pair<short, short>>>();
		res = 0;
		sol = false;
		s = false;

		for (short i = 0; i < l; i++) {
			for (short j = 0; j < r; j++) {
				scanf("%s", ary[i][j]);
				if (!s) {
					for (short k = 0; k < c; k++) {
						if (ary[i][j][k] == 'S') {
							q.push({ i,{j,k} });
							visited[i][j][k] = true;
							s = true;
						}
					}
				}
				
			}
		}

		while (!q.empty() && !sol) {
			short qsize = q.size();
			while (qsize--) {
				auto& loc = q.front();
				q.pop();
				short i = loc.first;
				short j = loc.second.first;
				short k = loc.second.second;
				// i if문
				if (i > 0) {
					if (!visited[i - 1][j][k]) {
						if (ary[i - 1][j][k] == 'E') {
							sol = true;
							break;
						}
						else if (ary[i - 1][j][k] == '.') {
							visited[i - 1][j][k] = true;
							q.push({ i - 1,{j,k} });
						}
					}
				}
				if (i < l - 1) {
					if (!visited[i + 1][j][k]) {
						if (ary[i + 1][j][k] == 'E') {
							sol = true;
							break;
						}
						else if (ary[i + 1][j][k] == '.') {
							visited[i + 1][j][k] = true;
							q.push({ i + 1,{j,k} });
						}
					}
				}
				// j if문
				if (j > 0) {
					if (!visited[i][j - 1][k]) {
						if (ary[i][j - 1][k] == 'E') {
							sol = true;
							break;
						}
						else if (ary[i][j - 1][k] == '.') {
							visited[i][j - 1][k] = true;
							q.push({ i,{j - 1,k} });
						}
					}
				}
				if (j < r - 1) {
					if (!visited[i][j + 1][k]) {
						if (ary[i][j + 1][k] == 'E') {
							sol = true;
							break;
						}
						else if (ary[i][j + 1][k] == '.') {
							visited[i][j + 1][k] = true;
							q.push({ i,{j + 1,k} });
						}
					}
				}
				// k if문
				if (k > 0) {
					if (!visited[i][j][k - 1]) {
						if (ary[i][j][k - 1] == 'E') {
							sol = true;
							break;
						}
						else if (ary[i][j][k - 1] == '.') {
							visited[i][j][k - 1] = true;
							q.push({ i,{j,k - 1} });
						}
					}
				}
				if (k < c - 1) {
					if (!visited[i][j][k + 1]) {
						if (ary[i][j][k + 1] == 'E') {
							sol = true;
							break;
						}
						else if (ary[i][j][k + 1] == '.') {
							visited[i][j][k + 1] = true;
							q.push({ i,{j,k + 1} });
						}
					}
				}
			}
			res++;
		}
		if (sol) printf("Escaped in %d minute(s).\n", res);
		else printf("Trapped!\n");
	}
	return 0;
}