[C++] 백준 7569번: 토마토

문제 바로가기

🎊문제 개관🎊

이전에 풀었던 7576번과 유사하다. 하지만 그 때보다 한 차원 증가했다. 나는 오른쪽과 같은 좌표계를 사용할 것이다.

// Vector3(h, r, c)
typedef tuple<int, int, int> Vector3;

---

🧨입력 조건🧨

2 ≤ N, M, H ≤ 100

---

🎢풀이🎢

📖 이전에 풀었던 7576번의 풀이를 많이 참고했다.

1. 토마토의 상태를 보여주는 3차원 배열 tomatos, 오늘 익은 토마토의 위치를 저장하는 큐 today, 내일 익을 토마토의 위치를 저장하는 큐 tomorrow가 있다.

2. 오늘 익은 토마토의 위치를 모두 한 번씩 방문하며 다음(3~5)을 반복한다.

  3. 인접한 토마토(neighbor)가 아직 안 익었다면, 내일 익을 토마토에 위치를 저장해둔다.

  4. 그 토마토의 상태는 익었다고 표시해둔다.

  5. 방문한 오늘 익은 토마토의 위치는 방문했을을 표시(mark)하고, 큐에서 지운다.

    - 표시하지 않으면 또 방문하게 된다.

6. 내일 익을 토마토가 더 이상 없을 때까지 위를 반복한다.

  - 내일이 되면, today = tomorrow를 하고 tomorrow는 초기화 한다.

7. 모든 토마토가 있었다면, 며칠이 걸렸는지 출력한다.

  - 그렇지 않다면, -1을 출력한다.

---

🎨보완요소🎨

예제 2를 넣고 돌려보면 4가 아닌 5를 출력했다. 이는 이미 모든 토마토가 익었음에도 내일 익을 토마토 큐가 남아있기 때문이었다. 아마도 중복으로 추가된 요소가 있었기 때문인 듯. 그래서 내일 익을 토마토가 더 이상 추가되지 않는다면, 날을 세지 않고 반복문 밖으로 내보냈다.

이 번 풀이에서는 함수를 적극 활용했다. 그래서 코드 가독성이 조금 좋아진 감이 있다. 하지만 너무 남용한 것이 아닌가 하는 걱정도 있는데, 코드 흐름을 따라가기엔 의사코드처럼 쓰여진 코드가 더 낫다 싶어서 앞으로 이런 코드 형태를 애용할 것 같다.

---

🎈정답코드🎈

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

using namespace std;

#define EL "\n"
#define FOR(i, K) for(int i = 0; i < K; i++)

// Vector3(H, R, C)
typedef tuple<int, int, int> Vector3;

int M, N, H;
int tomatos[100][100][100];
bool _mark[100][100][100];
queue<Vector3> today, tomorrow;
int adjoins[6][3] = { {-1, 0, 0}, {1, 0, 0}, {0, -1, 0}, {0, 1, 0}, {0, 0, -1}, {0, 0, 1} };

bool isValidPos(Vector3 pos) {
	if (get<0>(pos) < 0 || get<0>(pos) >= H)
		return false;
	if (get<1>(pos) < 0 || get<1>(pos) >= N)
		return false;
	if (get<2>(pos) < 0 || get<2>(pos) >= M)
		return false;
	return true;
}

int isUnripe(Vector3 pos) {
	return tomatos[get<0>(pos)][get<1>(pos)][get<2>(pos)] == 0;
}

void mark(Vector3 pos) {
	_mark[get<0>(pos)][get<1>(pos)][get<2>(pos)] = true;
}

bool isMarked(Vector3 pos) {
	return _mark[get<0>(pos)][get<1>(pos)][get<2>(pos)];
}

void LetTomatoRipe(Vector3 pos) {
	tomatos[get<0>(pos)][get<1>(pos)][get<2>(pos)] = 1;
}

Vector3 add(const Vector3& lhs, int rhs[]) {
	return make_tuple(get<0>(lhs) + rhs[0], get<1>(lhs) + rhs[1], get<2>(lhs) + rhs[2]);
}

bool isAllTomatosRipe() {
	FOR(h, H)
		FOR(r, N)
		FOR(c, M) {
		if (tomatos[h][r][c] == 0)
			return false;
	}
	return true;
}

void printTomatos() {
	FOR(h, H) {
		FOR(r, N) {
			FOR(c, M)
				cout << tomatos[h][r][c];
			cout << EL;
		}
		cout << EL;
	}
}


int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> M >> N >> H;
	FOR(h, H) {
		FOR(r, N) {
			FOR(c, M) {
				cin >> tomatos[h][r][c];
				if (tomatos[h][r][c] == 1)
					tomorrow.push(make_tuple(h, r, c));
			}
		}
	}

	int passedDays = 0;
	if (isAllTomatosRipe())
		goto OUT;
	while (tomorrow.size()) {
		bool isNotChanged = true;
		swap(today, tomorrow);
		while (isMarked(today.front())) {
			today.pop();
			if (today.empty())
				goto OUT;
		}
		while (today.size()) {
			Vector3 here = today.front();
			for (auto& adjoin : adjoins) {
				Vector3 neighbor = add(here, adjoin);
				if (isValidPos(neighbor) && isUnripe(neighbor)) {
					tomorrow.push(neighbor);
					LetTomatoRipe(neighbor);
					isNotChanged = false;
				}
			}
			mark(here);
			today.pop();
		}

		if (isNotChanged)
			goto OUT;

		passedDays++;
	}
OUT:
	if (isAllTomatosRipe())
		cout << passedDays << EL;
	else
		cout << -1 << EL;

	return 0;
}