백준 알고리즘 7569 (토마토(3D)) - C++, Python

[문제] 백준 알고리즘 7569 (토마토(3D))

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

7569번: 토마토

7576번 (토마토)의 3D ver. 문제이다.

> https://wlstyql.tistory.com/93

백준 알고리즘 7576 (토마토) - C++, Python

 

 

[문제 해결]

 

1. 가장 먼저 맵 자체에 0이 없으면 0 출력, 1일 때마다 Queue에 저장

2. 0이 있으면 6방향(x,y,z 축의 각각 +1,-1 방향)의 BFS를 진행한다. 

3. Queue와 While문으로 진행하며, 0인 지점마다 이전 값+1으로 누적하고 Queue에 push.

4. BFS를 모두 진행했는데 0이 있으면 -1 출력, 없으면 max-1 값 출력.

 

[C++]

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

struct XYZ {
	int x, y, z;
};
const int MAX = 101;
int m, n, h;
int map[MAX][MAX][MAX]; // 높이, 세로, 가로
int dx[6] = {1,0,0,-1,0,0};
int dy[6] = {0,1,0,0,-1,0};
int dz[6] = {0,0,1,0,0,-1};
queue<XYZ> q;

void print_max() {
	int max = map[0][0][0];
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < m; k++) {
				if (max < map[i][j][k]) {
					max = map[i][j][k];
				}
			}
		}
	}
	printf("%d", max-1);
}

bool exist_zero() {
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < m; k++) {
				if (!map[i][j][k]) {
					return true;
				}
			}
		}
	}
	return false;
}

void solve_bfs() {
	while (!q.empty()) {
		int x = q.front().x; // 현재 높이
		int y = q.front().y; // 현재 세로
		int z = q.front().z; // 현재 가로
		q.pop();
		for (int i = 0; i < 6; i++) {
			int nx = x + dx[i]; // 시도할 높이
			int ny = y + dy[i]; // 시도할 세로
			int nz = z + dz[i]; // 시도할 가로
			// nx, ny, nz가 범위 내에 있고
			if (0 <= nx && nx < h && 0 <= ny && ny < n && 0 <= nz && nz < m) {
				if (!map[nx][ny][nz]) { // 진행 안한 곳이면
					map[nx][ny][nz] = map[x][y][z] + 1;
					q.push({ nx, ny, nz });
				}
			}
		}
	}
}

int main() {
	memset(map, 0, sizeof(map));
	scanf("%d %d %d", &m, &n, &h);
	bool zero = false;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < m; k++) {
				scanf("%d", &map[i][j][k]);
				if (map[i][j][k] == 1) {
					q.push({ i, j, k });
				}
				else if (!map[i][j][k]) {
					zero = true;
				}
			}
		}
	}
	if (!zero) { // 이미 모두 익어있음
		printf("0");
		return 0;
	}
	solve_bfs(); // 안익은게 있다면 BFS 진행
	if (exist_zero()) { // 그래 다 익지 못하면
		printf("-1");
		return 0;
	}
	print_max(); // 다 익었으면 최대값-1 출력
	return 0;
}

 

[Python]

from collections import deque
import sys
input = sys.stdin.readline
m, n, h = map(int, input().split())
board = [[list(map(int, input().split())) for _ in range(n)] for _ in range(h)]
dx = (1, 0, 0, -1, 0, 0)
dy = (0, 1, 0, 0, -1, 0)
dz = (0, 0, 1, 0, 0, -1)
q = deque()

def print_max():
    _max = 0
    for i in range(h):
        for j in range(n):
            for k in range(m):
                if not board[i][j][k]:
                    return False
                if _max < board[i][j][k]:
                    _max = board[i][j][k]
    return _max-1

def solve_bfs():
    while q:
        x, y, z = q.popleft()
        for i in range(6):
            nx, ny, nz = x + dx[i], y + dy[i], z + dz[i]
            if 0 <= nx < h and 0 <= ny < n and 0 <= nz < m:
                if not board[nx][ny][nz]:
                    board[nx][ny][nz] = board[x][y][z] + 1
                    q.append((nx, ny, nz))
zero = False
for i in range(h):
    for j in range(n):
        for k in range(m):
            if board[i][j][k] == 1:
                q.append((i, j, k))
            elif not board[i][j][k]:
                zero = True
if not zero:
    print(0)
else:
    solve_bfs()
    out = print_max()
    if not out:
        print(-1)
    else:
        print(out)