대엉코딩

www.acmicpc.net/problem/7569

1. 풀이방법.

- 3차원배열을 이용한 bfs로 해결하였습니다.

- 처음에 input을 받을 때 전체토마토 수, 익은토마토 수를 체크한 후

- bfs를 돌면서 익을 때 마다 익은토마토수를 ++ 해주며,

- 큐가 비었을 때(종료조건) -> 익은토마토수 == 전체토마토수 이면 걸린시간을 출력

                                   -> 익은토마토수 != 전체토마토수 이면 (모두익힐 수 없음 -1출력)

2. 주의사항

- 3차원배열이므로 행,렬,높이 를 스스로 잘 설정하여 H,N,M 과 비교연산 등을 할 때 헷갈리지 않게 주의.

3. 나의코드

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

int tomatobox[101][101][101];//높이,세로행,가로행
bool visit[101][101][101];
int N, M, H;
int totaltomato;
int dx[6] = { 1,-1,0,0,0,0 }; //6방향탐색
int dy[6] = { 0,0,1,-1,0,0 };
int dz[6] = { 0,0,0,0,1,-1 };
struct tomato {
	int h, n, m;
};
queue<tomato> tmpq;
int timecount;
int tomatocount;

void inputs() {
	cin >> M >> N >> H;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++) {
				cin >> tomatobox[i][j][k];
				if (tomatobox[i][j][k] == 1) { //익은토마토
					totaltomato++;
					tomatocount++;
					tomatobox[i][j][k] = true;
					tmpq.push({ i,j,k });
				}
				if (tomatobox[i][j][k] == 0) { //익지않은 토마토
					totaltomato++;
				}
			}
		}
	}
}
bool sidecheck(int x, int y, int z) { //경계선 체크
	if (x >= 0 && x < H &&y >= 0 && y < N &&z >= 0 && z < M) return true;
	else return false;
}
void bfs() {
	while (1) {
		int qsize = tmpq.size();
		while (qsize--) {
			tomato thistomato = tmpq.front();
			tmpq.pop();
			for (int i = 0; i < 6; i++) {
				if (sidecheck(thistomato.h+dx[i], thistomato.n+dy[i], thistomato.m+dz[i])
					&&tomatobox[thistomato.h + dx[i]][thistomato.n + dy[i]][thistomato.m + dz[i]]==0 && visit[thistomato.h + dx[i]][thistomato.n + dy[i]][thistomato.m + dz[i]] == false) {
					visit[thistomato.h + dx[i]][thistomato.n + dy[i]][thistomato.m + dz[i]] = true;
					tomatocount++; //토마토가 익음
					tmpq.push({ thistomato.h + dx[i],thistomato.n + dy[i],thistomato.m + dz[i] });
				}
			}
		}
		if (tmpq.empty()) { //종료조건
			if (totaltomato == tomatocount) {
				cout << timecount << "\n";
				return;
			}
			else {
				cout << -1 << "\n";
				return;
			}
		}
		timecount++;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	bfs();

	return 0;
}

www.acmicpc.net/problem/6593

1. 풀이방법

- 3차원배열을 이용해야할 뿐 기초적인 BFS 문제입니다

- 범위검사와 BFS, 그리고 E에 도달하지 못했는데 큐가 비어있다면 더이상 갈 곳이 없는 것이므로

- 종료조건을 출력하고 나가면 됩니다.

2. 주의사항

- 구현에 몰두해서 짜다보니 메모리 초과가 떴는데 왜 그런가 봤더니 방문체크를 큐에서 꺼낼 때 하고 있었습니다.

- 그럴경우, 여러정점에서 동시방문하고자 할 수 있기 때문에 문제가 발생할 수 있습니다.

- BFS를 구현할 때는 방문체크를 큐에 넣을 떄 해줍시다.

3.나의코드

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

int L, R, C;
int seconds;
char sangbumbuilding[31][31][31];
bool visit[31][31][31];
int dx[6] = { 1,-1,0,0,0,0 }; //6방향 탐색
int dy[6] = { 0,0,1,-1,0,0 };
int dz[6] = { 0,0,0,0,1,-1 };
struct area {
	int x, y, z;
};

queue<area> tmpq;
area S;
area E;
area tmpa, tmparea;
bool inputs() {
	cin >> L >> R >> C;
	if (L == 0 && R == 0 && C == 0) return true;

	for (int i = 1; i <= L; i++) {
		for (int j = 1; j <= R; j++) {
			for (int k = 1; k <= C; k++) {
				visit[i][j][k] = false;
				cin >> sangbumbuilding[i][j][k];
				if(sangbumbuilding[i][j][k]=='S'){
					S.x = i; S.y = j; S.z = k;
				}
				if (sangbumbuilding[i][j][k] == 'E') {
					E.x = i; E.y = j; E.z = k;
				}
			}
		}
	}
	return false;
}

void bfs(area s) {
	tmpq.push(s);
	while (1) {
		if (tmpq.empty()) { cout << "Trapped!" << "\n"; return; }
		int tmpsize = tmpq.size();
		while(tmpsize--) { //1초당
			tmpa = tmpq.front();
			tmpq.pop();
			if (tmpa.x == E.x &&tmpa.y == E.y&&tmpa.z == E.z) {
				cout << "Escaped in "<<seconds<<" minute(s)."<<"\n"; return;
			}
			for (int i = 0; i < 6; i++) { //6방향탐색
				//범위 검사
				if (tmpa.x + dx[i] >= 1 && tmpa.x + dx[i] <= L && tmpa.y + dy[i] >= 1 && tmpa.y + dy[i] <= R && tmpa.z + dz[i] >= 1 && tmpa.z + dz[i] <= C) {
					if (sangbumbuilding[tmpa.x + dx[i]][tmpa.y + dy[i]][tmpa.z + dz[i]] == '.'|| sangbumbuilding[tmpa.x + dx[i]][tmpa.y + dy[i]][tmpa.z + dz[i]] == 'E') {
						if (visit[tmpa.x + dx[i]][tmpa.y + dy[i]][tmpa.z + dz[i]] == false) {
							tmparea.x = tmpa.x + dx[i]; tmparea.y = tmpa.y + dy[i]; tmparea.z = tmpa.z + dz[i];
							visit[tmparea.x][tmparea.y][tmparea.z] = true;
							tmpq.push(tmparea);
						}
					}
				}
			}
		}
		seconds++;
	}
}
void resetqueue() {
	while (1) {
		if (tmpq.empty()) return;
		tmpq.pop();
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	while (1) {
		resetqueue();
		if(inputs()) break;
		seconds = 0;
		bfs(S);
	}
	return 0;
}