[백준/C++] 7579번: 토마토

토마토가 모두 익는 최단시간을 계산하는 문제이다. 최소비용 문제이고, 간선의 가중치가 1이고 정점과 간선의 개수가 적으면 BFS로 푸는 문제라고 한다... input 순서를 바꾸면 틀리는데 이유를 모르겠다....

(반례모음) www.acmicpc.net/board/view/43699

 

#include<iostream>
#include<queue>
using namespace std;

int ans;
int M, N, H;
int map[101][101][101];
int noToma;
queue <pair<pair<int, int>, int>> q;

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


bool allRipe(void)
{

	for (int i = 0; i < H; i++){
		for (int j = 0; j < N; j++){
			for (int k = 0; k < M; k++){
				if (map[j][k][i] == 0) return false;
			}
		}
	}
	return true;

}

int bfs() {

	int day = 0;

	if (q.empty()) return -1;
	while (!q.empty()) {

		int qSize = q.size();
		for (int i = 0; i < qSize; i++) {
			int cx = q.front().first.first;
			int cy = q.front().first.second;
			int cz = q.front().second;

			for (int i = 0; i < 6; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				int nz = cz + dz[i];

				if (nx < 0 || ny < 0 || nz < 0 || nx >= N || ny >= M || nz >= H) continue;
				if (map[nx][ny][nz] == 0) {
					map[nx][ny][nz] = 1;
					q.push(make_pair(make_pair(nx, ny), nz));
				}
			}

			q.pop();

			if (q.size() == 0 && allRipe()) return day;
			else if (q.size() == 0 && !allRipe()) return -1;

		}
		day++;
	}
}

int main() {

	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 >> map[j][k][i];
				if (map[j][k][i] == 1) q.push(make_pair(make_pair(j, k), i));
				if (map[j][k][i] == -1) noToma++;
			}

		}
	}

	if (q.size() == M * N * H - noToma) {
		cout << 0;
	}
	else {
		int ans = bfs();
		cout << ans;
	}

	return 0;
}