백준 6593번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	128MB	골드 5

---

풀이

 밀린 문제 정리하기이다. 짬짬히 정리하는 나 자신. 이대로만 가자.

 

 문제만 읽어봐도 이 문제는 그래프 탐색문제임을 알 수 있다. 거기에 최단경로를 찾아야 하기 때문에 bfs를 쓰면 될 것이다. 특이한 점은 이 문제는 3차원 bfs라는 것이다. 2차원에서 시작점과 출구를 잇는 최단 경로를 찾는 것이 아닌, 3차원 공간에서 시작점과 출구를 이어야 하기 때문에, 위치정보를 저장하고 이동하는데 유의해야 한다.

코드

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int l, r, c;
vector<vector<string>> building;
tuple<int,int,int> st;

void input() {
	size_t s;
	building = vector<vector<string>>(l, vector<string>(r));

	for(int floor = 0; floor < l; floor++) {
		for(int row = 0; row < r; row++) {
			auto& line = building[floor][row];
			cin >> line;
			s = line.find('S');
			if (s != string::npos) {
				st = {floor, row, s};
			}
		}
	}
}

int bfs() {
	int res = -1;
	queue<tuple<int,int,int,int>> q; // x, y, z, dist;
	int dx[] = {0, 1, 0, -1, 0, 0};
	int dy[] = {-1, 0, 1, 0, 0, 0};
	int dz[] = {0, 0, 0, 0, 1, -1};

	auto& [z, y, x] = st;

	q.push({x, y, z, 0});
	
	while(!q.empty()) {
		auto [cx, cy, cz, cdist] = q.front();
		q.pop();

		if (building[cz][cy][cx] == 'E') {
			res = cdist;
			break;
		}

		for(int d = 0; d < 6; d++) {
			int nx = cx + dx[d], ny = cy + dy[d], nz = cz + dz[d];

			if (nx < 0 || nx >= c ||
				ny < 0 || ny >= r ||
				nz < 0 || nz >= l) {
				continue;
			}

			auto& next_step = building[nz][ny][nx];

			if (next_step == '#' ||
				next_step == 'S' ||
				next_step == '-') {
					continue;
				}

			if (next_step == '.') next_step = '-';	
			q.push({nx, ny, nz, cdist + 1});
		}
	}
	return res;
}

void sol() {
	int dist = bfs();
	if (dist == -1) {
		cout << "Trapped!";
	}
	else {
		cout << "Escaped in " << dist << " minute(s).";
	}
	cout << endl;
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	while (true) {
		cin >> l >> r >> c;
		if (!l && !r && !c) break;
		input();
		sol();
	}
}