백준7569 - 토마토

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

7569번: 토마토

3차원 행렬을 이용한 bfs문제였다. 익은 토마토를 기점으로 안 익은 토마토를 찾아내면 되어서 bfs를 사용하였다.

 

처음에 토마토의 정보를 입력 받을 때 익은 토마토와 안 익은 토마토를 구분하여 입력 받는다. 입력으로 안 익은 토마토가 들어오면 안 익은 토마토의 갯수를 미리 세고 익은 토마토가 들어오면 bfs를 수행할 위치로 기억해둔다. 안 익은 토마토의 갯수가 0개이면 bfs를 진행하지 않고 0개가 아니라면 bfs를 진행한다.

 

토마토는 익은 토마토를 기점으로 하여 6방향으로 익는다. 각각의 케이스마다 탐색을 수행하는 동안 해당 탐색이 몇번째 일 수 인지 기록한다. 다음 탐색 위치가 안 익은 토마토면 현재 일수 + 1을 하여 다음 위치를 저장하고 안 익은 토마토의 갯수도 -1을 한다. bfs를 사용하기 때문에 여러 개의 토마토가 동시에 한 칸에 접근해도 해당 칸은 방문 여부에 따라서 방문한 칸이라면 탐색을 진행하지 않고 방문하지 않은 칸이면 탐색을 진행한다.

 

문제에서는 토마토가 다 익는 최소 일 수를 구하라고 하였다. bfs로 탐색이 종료된 시간이 최소 일 수 이기 때문에 max함수를 이용하여 가장 큰 일 수를 찾았다. 

 

#include <iostream>
#include <queue>
#include <algorithm>
#define	MAX 101
using namespace std;

class Point {
public:
	int x, y, z, w;
	Point(int x, int y, int z, int w) {
		this->x = x;
		this->y = y;
		this->z = z;
		this->w = w;
	}
};

int time = 0; //토마토가 모두 익는데 걸리는 시간
int m, n, o; //세로, 가로, 층
int cnt = 0; //안 익은 토마토의 갯수
int mat[MAX][MAX][MAX]; //토마토의 정보
bool visit[MAX][MAX][MAX] = { false, };
queue<Point> q;

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

void bfs() {
	while (!q.empty()) {
		//토마토의 위치와 해당 토마토의 일수를 저장하고 제일 첫 원소 삭제
		int x = q.front().x;
		int y = q.front().y;
		int z = q.front().z;
		int w = q.front().w;
		q.pop();

		time = max(time, w);

		for (int i = 0; i < 6; i++) { //6방향
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nz = z + dz[i];

			if (1 <= nx && nx <= n && 1 <= ny && ny <= m && 1 <= nz && nz <= o && !visit[nx][ny][nz]) { //유효한 좌표 범위이고 방문하지 않은 칸이면
				if (mat[nx][ny][nz] == 0) { //다음에 이동할 칸이 안 익은 토마토면
					mat[nx][ny][nz] = 1; //익은 토마토로 바꾸고
					visit[nx][ny][nz] = true; //다음에 이동할 칸을 방문 처리하고
					q.push(Point(nx, ny, nz, w + 1)); //해당 칸에서 일수를 늘려 재탐색
					cnt--; //안 익은 토마토 갯수 감소
				}
			}
		}
	}
}

int main() {
	cin >> m >> n >> o;

	for (int k = 1; k <= o; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> mat[i][j][k];
				if (mat[i][j][k] == 0) { //안 익은 토마토면
					cnt++; //안 익은 토마토 갯수 늘리기
				}
				else if (mat[i][j][k] == 1) { //익은 토마토면
					q.push(Point(i, j, k, 0)); //익은 토마토의 위치를 큐에 저장
					visit[i][j][k] = true; //방문처리
				}
			}
		}
	}

	if (cnt == 0) { //안 익은 토마토의 갯수가 0이면
		cout << 0; //모두 익었다.
	}
	else { //안 익은 토마토가 한 개라도 있다면 
		bfs(); //bfs를 실행
		if (cnt == 0) { //bfs결과 안 익은 토마토가 한 개도 없으면
			cout << time; //토마토가 모두 익는데까지 걸린 시간을 출력
		}
		else { //bfs결과 안 익은 토마토가 존재하면
			cout << -1; //모두 익을 수 없다고 출력
		}
	}
}