[백준 7569/C++] 토마토

1. 문제

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

7569번: 토마토

---

2. 문제 풀이

#include <iostream>
#include <bits/stdc++.h>
#pragma warning (disable:4996)
#define X first
#define Y second

using namespace std;

int board[105][105][105];
int dist[105][105][105];
int nx[6] = { 0,0,1,0,-1,0 };
int ny[6] = { 0,0,0,1,0,-1 };
int nz[6] = { 1,-1,0,0,0,0 };

int M, N, H;
int ans;

int main(void) {
	iostream::sync_with_stdio(0);
	cin.tie(0);
	cin >> M >> N >> H;
	queue<tuple<int,int,int>> Q;
	for (int i = 0; i < H; i++)
		for (int j = 0; j < N; j++)
			fill(dist[i][j], dist[i][j] + M, -1);
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++) {
				cin >> board[i][j][k];
				if (board[i][j][k] == 1) {
					Q.push({ i,j,k });
					dist[i][j][k] = 0;
				}
			}
		}
	}
	while (!Q.empty()) { // 0 1 2
		auto cur = Q.front(); Q.pop();
		for (int dir = 0; dir < 6; dir++) {
			int dx = get<1>(cur) + nx[dir];
			int dy = get<2>(cur) + ny[dir];
			int dz = get<0>(cur) + nz[dir];
			if (dx < 0 || dx >= N || dy < 0 || dy >= M || dz < 0 || dz >= H) continue;
			if (board[dz][dx][dy] == -1 || dist[dz][dx][dy] >= 0) continue;
			Q.push({ dz,dx,dy });
			dist[dz][dx][dy] = dist[get<0>(cur)][get<1>(cur)][get<2>(cur)] + 1;
		}
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++) {
				if (board[i][j][k] == 0 && dist[i][j][k] == -1) {
					cout << -1;
					return 0;
				}
				ans = max(ans, dist[i][j][k]);
			}
		}
	}
	cout << ans;
}

---

3. 문제 평가 및 해설

이전에 올렸던 백준 7576 문제의 3차원 버전이다. 다음 링크는 2차원 토마토 문제이다.

https://devhater.tistory.com/25

[백준 7576/C++] 토마토

처음 코드를 짜고 분명히 TC도 다 통과하고, 백준 질문 시판의 반례도 옳게 나왔는데 2%에서 "틀렸습니다!"가 계속 나왔다. 결국, 코드를 지우고 처음부터 다시 짰다.. 아직까지 원인을 모르겠다. 문제 풀이는 2차원 토마토에서 3차원으로 차원을 확장한 것과 같다. 간단히 설명하자면 다음과 같다.

1. 3차원은 상하좌우 + 위아래 까지 생각해야 하므로, 이동할 수 있는 경우가 6가지이다. 따라서 nx,ny,nz 배열도 6개로 설정해주어야 한다.

2. 이동할 수 있는 통로가 6가지로 늘었으니, 예외처리도 늘려야 한다. 높이에 대한 두 가지 예외처리(음수이거나, H를 넘어섰을 때)를 해주면 된다. 

3. 익지 않은 토마토가 존재한다면, 종료하고 -1를 출력해야한다.

실수할 수 있는 부분은 M,N을 착각하거나, 예외처리를 해주지 않은 경우가 있겠다. 혹시라도 독자분들 중에 내 틀린 소스코드 중 문제점(?)을 찾고 싶다면 다음 링크를 참고하면 된다.. 아직까지 맞왜틀을 외치는 중 이지만, 다시 짠 코드가 훨씬 깔끔해서 잊고 넘어갈 생각이다.

https://www.acmicpc.net/source/64657162

로그인