[BOJ 7569 // C++] 토마토

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 7569번 문제인 토마토이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/7569

7569번: 토마토

2차원배열에서 주어진 점에서 가장 멀리 떨어진 점을 찾는 문제의 3차원 버전이라고 볼 수 있겠다.

성분을 하나 추가해서 확장하면 그대로 풀린다.

 

글쓴이는 tuple<int,int,int>를 담는 queue를 만들어 DFS로 풀어보았다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
#include <tuple>
using std::queue;
using std::cin;
using std::cout;
using std::tuple;
using std::make_tuple;

queue<tuple<int, int, int>> que;
using std::cin;
using std::cout;

int tomato[100][100][100];

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

int main()
{ // 입력: 3차원 토마토 배열을 만들면서 토마토가 있는 위치를 queue에 넣는다
    int x, y, z;
    cin >> x >> y >> z;
    int temp;
    for (int k = 0;k < z;k++) {
        for (int j = 0;j < y;j++) {
            for (int i = 0;i < x;i++) {
                cin >> temp;
                tomato[i][j][k] = temp;
                if (temp == 1) {
                    que.push(make_tuple(i,j,k));
                }
            }
        }
    }
    int ans=1;
    while (!que.empty()) { // BFS
        tuple<int, int, int> current = que.front();
        que.pop();
        for (int i = 0;i < 6;i++) {
            int xx = std::get<0>(current) + dx[i];
            int yy = std::get<1>(current) + dy[i];
            int zz = std::get<2>(current) + dz[i];
            if (xx >= 0 and xx < x and yy >= 0 and yy < y and zz >= 0 and zz < z) {
                if (tomato[xx][yy][zz] == 0) {
                    tomato[xx][yy][zz] = tomato[std::get<0>(current)][std::get<1>(current)][std::get<2>(current)]+1;
                    que.push(make_tuple(xx, yy, zz));
                    if (tomato[xx][yy][zz] > ans) ans = tomato[xx][yy][zz];
                }
            }
        }
    }
    for (int k = 0;k < z;k++) { // 안 익은 토마토가 남아있는지 확인하기
        for (int j = 0;j < y;j++) {
            for (int i = 0;i < x;i++) {
                if (tomato[i][j][k] == 0) {
                    ans = 0;
                }
            }
        }
    }
    cout << ans-1;

    return 0;
}