백준 7569번 C++

백준 7569번 토마토

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

7569번: 토마토

정답 코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
vector<vector<int>> dir = { {-1,0,0}, {1,0,0}, {0,1,0}, {0,-1,0}, {0,0,1}, {0,0,-1} };
queue<pair<int, pair<int, int>>>q;
int arr[101][101][101];
bool vis[101][101][101];
int time1[101][101][101];
int bfs(int M, int N, int H) {


	while (!q.empty()) {
		pair<int, pair<int, int>>cur = q.front();
		q.pop();
		for (int x = 0; x < 6; x++) {
			int mx = cur.first + dir[x][0];
			int my = cur.second.first + dir[x][1];
			int mz = cur.second.second + dir[x][2];
			if (mx < 0 || my < 0 || mz < 0 || mx >= H || my >= N || mz >= M) //범위를 벗어날 때
				continue;
			if (time1[mx][my][mz] >= 0)
				continue;
			if (arr[mx][my][mz] == 0) {
				q.push({ mx,{my,mz} });
				time1[mx][my][mz] = time1[cur.first][cur.second.first][cur.second.second] + 1;
				arr[mx][my][mz] = 1; // 토마토가 익었음
			}
		}
	}




	int max = -1;
	for (int i = 0; i < H; i++) { // 걸린 시간 찾기
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++)
			{
				if (max < time1[i][j][k])
					max = time1[i][j][k];
			}
		}
	}
	for (int i = 0; i < H; i++) { // 걸린 시간 찾기
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++)
			{
				if (arr[i][j][k] == 0)
					return -1;
			}
		}
	}

	return max;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	for (int i = 0; i < 101; i++) {
		for (int j = 0; j < 101; j++) {
			for (int k = 0; k < 101; k++)
				time1[i][j][k] = -1;
		}
	}
	int M, N, H;
	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 >> arr[i][j][k];
				if (arr[i][j][k] == 1) {
					q.push({ i,{j,k} });
					time1[i][j][k] = 0;
				}
			}
		}
	}
	cout << bfs(M, N, H);

}

문제 풀이

bfs를 이용해서 풀었습니다. 주어진 형태가 3차원이다 보니 모두 3차원 배열을 만들었고 움직일 수 있는 것들도 좌표를3개를 사용했습니다.
먼저 time배열을 -1로 초기화한 후 arr배열에 입력을 받고 입력값이 1이면 그때의 좌표값을 큐에넣고 time배열값을 0으로 바꾸었습니다. 나중에 for문을 돌려서 1을 찾는 반복성을 없애기 위함입니다.
그 후 bfs를 돌려주고 배열의 범위를 벗어나거나 time값이 0보다 큰 이미 방문한 곳은 continue시켰습니다.
arr[mx][my][mz]값이 0일 경우에는 토마토가 익을 수 있는 곳이므로 큐에 좌표값을 삽입, time배열값 변경, arr값도 1로 변경(토마토가 익음)하였습니다.
마지막으로 time배열을 돌리면서 최솟갑을 찾아주고
arr배열을 돌려서 만약 0이 있는 경우(토마토가 다 안익은 것이므로 실패)를 체크해줍니다.