[BOJ] C++ 6593 "상범 빌딩" 문제 풀이 _ nov

#INFO

난이도 : GOLD5

문제유형 : BFS

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

6593번: 상범 빌딩

---

#SOLVE

최근에 풀었던 BOJ7569토마토 문제와 거의 같은 문제였다. 다른 점 이라면 여러번 입력을 받는다는 정도..? 하지만 상범빌딩 문제를 풀며 부족했던 부분이 많이 보여 다시 정리해 보고자 한다.

우선 6가지 방향으로 이동하기에 이동 변수를 잘 설정해 준다.

int dx[6] = {0, 0, 1, -1, 0, 0};
int dy[6] = {1, -1, 0, 0, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};

 

다음으로 BFS풀이에 필요한 기본 변수들을 선언해 준다.

char building : 상범 빌딩의 정보를 저장할 배열이다.

int isBlocked : 각 빌딩의 칸이 막혀있는지 여부를 저장할 배열이다. ( 0 : 뚫림 1 : 막힘 )

int distance : 특정 칸 까지의 거리 정보를 저장할 배열이다.

bool isVisited : BFS 알고리즘에서 방문 여부를 저장할 배열이다.

	int L, R, C;
	while(1){
		cin >> L >> R >> C;
		if(L == 0 && R == 0 && C == 0) break;
		queue<pair<int, pair<int, int>>> Q;				
		char building[MAX][MAX][MAX];
		int isBlocked[MAX][MAX][MAX];
		int distance[MAX][MAX][MAX];
		bool isVisited[MAX][MAX][MAX];

 

여러 케이스 루프를 돌 것 이기에 각 배열의 원소를 초기화 시켜준다. 처음에 테스트 케이스를 제출했을 때 이 부분을 빼먹어서 통과하지 못했다.

		for(int h = 0; h < L; h++){
			for(int r = 0; r < R; r++){
				for(int c = 0; c < C; c++){
					isBlocked[h][r][c] = 0;
					distance[h][r][c] = 0;
					isVisited[h][r][c] = false;
				}
			}
		}

 

isEscape 변수는 'E' 종점을 도달했는 지 여부를 판별할 변수이다. 다음으로 3중 for문을 돌면서 'S' 시작점을 만나면 방문표시를 한 후 큐에 넣어주고, '#' 이동 불가칸을 만나면 isBlocked[h][r][c]를 1로 초기화시켜 막혀있는 공간임을 표시한다.

		bool isEscape = false;
		for(int h = 0; h < L; h++){
			for(int r = 0; r < R; r++){
				for(int c = 0; c < C; c++){
					char temp;
					cin >> temp;
					building[h][r][c] = temp;
					// 'S' 스타트 구역. 방문표시를 한 뒤, 큐에 위치를 푸시한다.
					if(temp == 'S'){
						isVisited[h][r][c] = true;
						Q.push({h, {r, c}});
					}
					// '#' 막혀있는 공간이 나올 경우 빌딩의 원소를 1(지나갈 수 없음)로 설정
					else if(temp == '#'){
						isBlocked[h][r][c] = 1;
					}
				}
			}
		}

 

평범한 BFS 풀이이다. 'E' 출구를 만나면 "Escaped in () minute(s)." 문자를 출력하고, isEscape를 true로 만든 뒤 탈출한다. 만약 isEscape가 false인 상태로 반복문을 탈출했다면, 출구에 도달하지 못했다는 뜻 이기에 "Trapped!" 문자열을 출력한다.  

		while(!Q.empty()){
			if(isEscape) break;
			auto cur = Q.front();
			Q.pop();
			for(int dir = 0; dir < 6; dir++){
				int nx = cur.second.first + dx[dir];
				int ny = cur.second.second + dy[dir];
				int nz = cur.first + dz[dir];
				if(nx < 0 || nx >= R || ny < 0 || ny >= C || nz < 0 || nz >= L) continue;
				if(isVisited[nz][nx][ny] == true || isBlocked[nz][nx][ny] == 1) continue;
				distance[nz][nx][ny] = distance[cur.first][cur.second.first][cur.second.second] + 1;				
				if(building[nz][nx][ny] == 'E'){
					cout << "Escaped in " << distance[nz][nx][ny] << " minute(s)." << '\n';
					isEscape = true;
					break;
				} 				
				Q.push({nz, {nx, ny}});
				isVisited[nz][nx][ny] = 1;
			}

		}
        
        while(!Q.empty()) Q.pop();
		if(!isEscape) cout << "Trapped!" << '\n';

---

#CODE

#include <bits/stdc++.h>
using namespace std;
const int MAX = 31;
int dx[6] = {0, 0, 1, -1, 0, 0};
int dy[6] = {1, -1, 0, 0, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};

int main(int argc, char* argv[]) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int L, R, C;
	while(1){
		cin >> L >> R >> C;
		if(L == 0 && R == 0 && C == 0) break;
		queue<pair<int, pair<int, int>>> Q;				
		char building[MAX][MAX][MAX];
		int isBlocked[MAX][MAX][MAX];
		int distance[MAX][MAX][MAX];
		bool isVisited[MAX][MAX][MAX];
		
		for(int h = 0; h < L; h++){
			for(int r = 0; r < R; r++){
				for(int c = 0; c < C; c++){
					isBlocked[h][r][c] = 0;
					distance[h][r][c] = 0;
					isVisited[h][r][c] = false;
				}
			}
		}
		
		bool isEscape = false;
		for(int h = 0; h < L; h++){
			for(int r = 0; r < R; r++){
				for(int c = 0; c < C; c++){
					char temp;
					cin >> temp;
					building[h][r][c] = temp;
					// 'S' 스타트 구역. 방문표시를 한 뒤, 큐에 위치를 푸시한다.
					if(temp == 'S'){
						isVisited[h][r][c] = true;
						Q.push({h, {r, c}});
					}
					// '#' 막혀있는 공간이 나올 경우 빌딩의 원소를 1(지나갈 수 없음)로 설정
					else if(temp == '#'){
						isBlocked[h][r][c] = 1;
					}
				}
			}
		}

		while(!Q.empty()){
			if(isEscape) break;
			auto cur = Q.front();
			Q.pop();
			for(int dir = 0; dir < 6; dir++){
				int nx = cur.second.first + dx[dir];
				int ny = cur.second.second + dy[dir];
				int nz = cur.first + dz[dir];
				if(nx < 0 || nx >= R || ny < 0 || ny >= C || nz < 0 || nz >= L) continue;
				if(isVisited[nz][nx][ny] == true || isBlocked[nz][nx][ny] == 1) continue;
				distance[nz][nx][ny] = distance[cur.first][cur.second.first][cur.second.second] + 1;				
				if(building[nz][nx][ny] == 'E'){
					cout << "Escaped in " << distance[nz][nx][ny] << " minute(s)." << '\n';
					isEscape = true;
					break;
				} 				
				Q.push({nz, {nx, ny}});
				isVisited[nz][nx][ny] = 1;
			}

		}
		while(!Q.empty()) Q.pop();
		if(!isEscape) cout << "Trapped!" << '\n';
	}
	
	return 0;
}