[백준/c++] 6593번 - 상범 빌딩

[ 참고 ]

전형적인 bfs문제로 3차원 bfs문제중 유명한 7569번 토마토와 별반 다르지 않다.

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

7569번: 토마토

 

 

[ 문제 ]

 

 

 

[ 구현 ]

 

dx,dy,dz로 3차원, 동서남북상하를 이동할 수 있도록 준비해두고 

queue<tuple<int,int,int,int>>을 이용한 bfs로 풀었다.

 

주의해야할 점은 주어지는 정보가 층, 행, 열의 순으로 주어지고

queue에 집어넣고, 가능한 범위를 벗어나지 않는지 검사할때도 이 규칙성을 잘 가지고 대입해야한다.

(매번 헷갈림..)

 

처음에는 bfs 파라미터를 a,b,c,cnt로 받았었다가 l,r,c의 c와 겹치는 줄도 모르고 해멨다..

->d,e,f로 변경

 

또 x,y,z축의 정보이외에도 내부적으로 변수를 하나 더 따로 저장하여 원하는 정보인 minute을 표현하도록 하였다.

 

전체적으로 bfs는 while(for())의 형태를 띄므로 다 검사하고 'E'에 도달했을 때의 상태를 flag로 관리하였다.(따라서 bfs문 안에서 'E'를 만나지 않고 벽에 막힌 상태로 종료되는 경우 main문에서 flag를 통해 "Trapped!"를 출력해주었다)

 

E를 찾았음에도 그냥 계속해서 bfs를 끝까지 돌게끔 신경쓰지 않고 구현한다면

while문 밖에 그냥 cout << "Trapped!"<<'\n';의 형태로 구현해도 상관은 없을 듯하다.

 

마지막으로 0,0,0이 주어질 때까지 계속해서 정보가 주어지므로 방문한 칸인지 아닌지를 저장하는 정보를 bfs가 한번 끝날 때마다 memset을 통해 초기화 해주었다.

 

 

[ 코드 ]

 

#include <iostream>
#include <queue>
#include <cstring>
#include <tuple>

using namespace std;


int l, r, c;
bool visited[31][31][31];
int dx[6] = { -1,0,0,1,0,0};
int dy[6] = { 0,1,-1,0,0,0 };
int dz[6] = { 0,0,0,0,1,-1 };
char arr[31][31][31];
int ans = 0;
bool flag;//E발견시 bfs종료

void bfs(int d, int e, int f, int cnt) {
	flag = true;
	queue<tuple<int,int,int,int>> q;
	q.push({ d,e,f,cnt });
	visited[d][e][f] = true;
	

	while (!q.empty() && flag) {
		
		int x = get<0>(q.front());
		int y = get<1>(q.front());
		int z = get<2>(q.front());
		int w = get<3>(q.front());
		q.pop();

		for (int i = 0; i < 6; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nz = z + dz[i];
			int nw = w + 1;
			if (nx < 0 || ny < 0 || nz<0 || nx >= r || ny >= c || nz >= l) continue;

			if (!visited[nx][ny][nz]) {
				visited[nx][ny][nz] = true;

				if (arr[nx][ny][nz] == 'E') {
					cout << "Escaped in " << nw << " minute(s)." << '\n';
					flag = false;
					break;
				}
				if (arr[nx][ny][nz] == '.') {
					q.push({ nx,ny,nz,nw });
				}

			}
		}
		if (!flag) break;
	}
}

int main() {

	int t1, t2, t3;
	//l층 r행 c열
	//i   j   k
	//z   x   y

	while(true) {
	cin >> l >> r >> c;
	if (l == 0 && r == 0 && c == 0) break;

	for (int i = 0; i < l; i++) {
		for (int j = 0; j < r; j++) {
			for (int k = 0; k < c; k++) {
				cin >> arr[j][k][i];
				if (arr[j][k][i] == 'S') {
					t1 = j; t2 = k; t3 = i;
				}
			}
		}
	}

	bfs(t1, t2, t3,0);
	
	if (flag) cout << "Trapped!" << endl;
	flag = true;
	memset(visited, false, sizeof(visited));

	}



	return 0;
}

 

 

[ 마무리 및 느낀 점 ]

한동안 dp문제만 풀고 bfs쪽은 손을 대지 않아서 좀 가물가물해진 감이 있어 요즘 조금씩 풀어보고 있다.

슬슬 단순 구현을 넘어서서 조금씩 조건이 까다로워지는 문제에 대한 구현을 시도해봐야 실력이 늘 것 같다.