(백준 6593번 상범빌딩 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 6

3차원이라 복잡해보이지만 원리는 동일한 상범빌딩 문제를 풀어보았다.

 

백준 6593번

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

6593번: 상범 빌딩

 

#include <iostream>
#include <queue>
#include <string>
using namespace std;

constexpr int MAX_N = 31;

class Building {
public:
	int L, R, C;
	pair<pair<int, int>, int> start, end;
	int dir_l[6] = { 1, 0, -1, 0, 0, 0 };
	int dir_r[6] = { 0, 1, 0, -1, 0, 0 };
	int dir_c[6] = { 0, 0, 0, 0, 1, -1 };
	int arr[MAX_N][MAX_N][MAX_N];
	
	Building(int L, int R, int C) : L(L), R(R), C(C) {};

	void getInfo() {
		for (int i = 0; i < L; i++) {
			for (int j = 0; j < R; j++) {
				string st; cin >> st; 
				for (int k = 0; k < C; k++) {
					// ★ {} 괄호 잘 닫아주기
					if (st[k] == 'S') {
						start.first.first = i; start.first.second = j; start.second = k;
					}

					if (st[k] == 'E') {
						end.first.first = i; end.first.second = j; end.second = k;
					}
					
					if(st[k] == '.' || st[k] == 'S' || st[k] == 'E') arr[i][j][k] = 0;
					else if(st[k] == '#') arr[i][j][k] = -1;
				}
			}
		}
	}
	
	bool isInside(int l, int r, int c) {
		if (l >= L || l < 0 || r >= R || r < 0 || c >= C || c < 0) return false;
		return true;
	}

	void escape(){
		int startL = start.first.first; int startR = start.first.second; int startC = start.second;
		int endL = end.first.first; int endR = end.first.second; int endC = end.second;
		int ans = escape(startL, startR, startC, endL, endR, endC);
		if (ans == -1) cout << "Trapped!\n";
		else cout << "Escaped in " << ans << " minute(s).\n";
		return;
	}
private:
	int escape(int stL, int stR, int stC, int  eL, int eR, int eC) {
		pair<pair<int, int>, int> curr = start;
		queue <pair<pair<int, int>, int>> Q;
		Q.push(start);

		int level = 0; 
		while (!Q.empty()) {
			// ★ 최소거리를 구할 땐 qsize를 이용하기
			int qsize = Q.size();
			for (int t = 0; t < qsize; t++) {
				int currL = Q.front().first.first;
				int currR = Q.front().first.second;
				int currC = Q.front().second;
				arr[currL][currR][currC] = -1;
				Q.pop();

				for (int i = 0; i < 6; i++) {
					int nextL = currL + dir_l[i];
					int nextR = currR + dir_r[i];
					int nextC = currC + dir_c[i];

					if (isInside(nextL, nextR, nextC) && arr[nextL][nextR][nextC] != -1) {
						arr[nextL][nextR][nextC] = -1;
						Q.push(make_pair(make_pair(nextL, nextR), nextC));
						if (nextL == eL && nextR == eR && nextC == eC) return ++level;
					}
				}
			}
			level++;
		}
		return -1;
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int L, R, C;
	while (cin >> L >> R >> C && L + R + C != 0) {
		Building b(L, R, C);
		b.getInfo();
		b.escape();
	}
	return 0;
}

 

⭐ 교훈 ⭐

답에 맞춰 로직을 바꾸면 안된다. 예시 입력은 통과할지 몰라도 전체 테스트 셋을 통과하자 못하기 때문!!!

로직을 잘 살펴보면서 이상한 곳이 없는지 확인하도록 하자!