［Ｃ＋＋ 백준알고리즘] 백준 7569: 토마토

 

 

>> 문제 전략 <<

• 하루가 지나면, 익은 토마토의 주변이 동시에 익으므로 BFS를 활용
• 가로, 세로, 높이가 존재  =>  전역변수로 long long 형 3차원배열 두개 선언(방문 확인, 토마토 박스)
• 세 개의 인자를 받아야 하는 Queue를 선언해야함, std::tuple 활용 >> 3개의 인자를 동시에 넣을 수 있음
• 뿐만 아니라, 날짜를 계산해야함 >> std::pair 안에 std::tuple 과 count 변수를 넣어줌 >> count를 통해 같은 날에 익은 토마토를 구분 가능.
• count의 값은, 값이 최대가 될 때 마지막으로 토마토가 익는 날짜인 것을 알 수 있음.

 

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

long long box[101][101][101] = {};
long long vi[101][101][101] = {};

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	
	int m, n, h;
	std::queue<std::pair<std::tuple<int, int, int>, int>> q;

	std::cin >> m >> n >> h;

	int tomaNum = 0;
	for (int i{0} ; i < h ; i++) {
		for (int j{ 0 }; j < n; j++) {
			for (int k{ 0 }; k < m; k++) {
				std::cin >> box[i][j][k];
				if (box[i][j][k] == 1) {
					q.push(std::make_pair(std::make_tuple(i, j, k), 0));
				}
				if(box[i][j][k] != -1) tomaNum++;
			}
		}
	}

	int count = 0;
	while (!q.empty()) {
		std::tuple<int, int, int> t = q.front().first;
		int num = q.front().second;

		int i = std::get<0>(t);
		int j = std::get<1>(t);
		int k = std::get<2>(t);

		tomaNum--;
		count = std::max(count, num);
		
		q.pop();

		if (std::get<0>(t) != 0 && !vi[i - 1][j][k] && box[i - 1][j][k] == 0) {
			q.push(std::make_pair(std::make_tuple(i - 1, j, k), num + 1));
			vi[i - 1][j][k] = true;
		}
		if (std::get<1>(t) != 0 && !vi[i][j-1][k] && box[i][j-1][k] == 0) {
			q.push(std::make_pair(std::make_tuple(i, j-1, k), num + 1));
			vi[i][j-1][k] = true;
		}
		if (std::get<2>(t) != 0 && !vi[i][j][k-1] && box[i][j][k-1] == 0) {
			q.push(std::make_pair(std::make_tuple(i, j, k-1), num + 1));
			vi[i][j][k-1] = true;
		}
		if (std::get<0>(t) != h-1 && !vi[i+1][j][k] && box[i + 1][j][k] == 0) {
			q.push(std::make_pair(std::make_tuple(i + 1, j, k), num + 1));
			vi[i + 1][j][k] = true;
		}
		if (std::get<1>(t) != n-1 && !vi[i][j+1][k] && box[i][j + 1][k] == 0) {
			q.push(std::make_pair(std::make_tuple(i, j + 1, k), num + 1));
			vi[i][j + 1][k] = true;
		}
		if (std::get<2>(t) != m-1 && !vi[i][j][k + 1] && box[i][j][k + 1] == 0) {
			q.push(std::make_pair(std::make_tuple(i, j, k + 1), num + 1));
			vi[i][j][k + 1] = true;
		}
	}

	if (tomaNum != 0) std::cout << -1 << "\n";
	else std::cout << count << "\n";
}

 

 

참고 : std::tuple은 접근방법이 std::pair와는 다르다.

 

std::get<tuple인자의 번호>(tuple 변수명) 으로 인덱스를 조회할 수 있음.