[BaekJoon 7569번] 토마토(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

7569번: 토마토

 

 

[문제 설명]

 

 

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

 

[입력]

 

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

 

 

[출력]

 

 

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

 

 

[입출력 예]

 

 

입력	출력
5 3 1 0 -1 0 0 0 -1 -1 0 1 1 0 0 0 1 1	-1
5 3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0	4
4 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 1 1 1 -1	0

 

 

[문제 풀이]

 

쉬운 문제지만 3차원 배열을 사용해서 낯설었던 문제

 

저장될 때부터 모든 토마토가 익어 있는 상태면 0을 출력해야한다.의 경우 flag를 사용하였다.

flag를 false로 초기화한 뒤 입력을 받을 때 익지 않은 토마토의 입력을 받으면 true로 값을 변경시켜준다.

입력을 다 받았을 때 flag를 확인하여 false로 남아있다면 익은 토마토만 있는 것이다.

 

그리고 이문제는 3차원 배열이기 때문에 위, 아래 , 왼쪽, 오른쪽, 앞, 뒤 이동을 생각해야한다.

(3차원이 되면서 이동할 수 있는 경우의 수가 2개 늘었다.)

그래서 이동해야하는 경우를 다음과 같이 선언했다.

int dh[6] = { 1, -1, 0, 0, 0, 0};
int dn[6] = { 0, 0, 0, 0, 1, -1}; 
int dm[6] = { 0, 0, -1, 1,0, 0};

 

그리고 처음에 입력을 받을 때 익은 토마토의 경우 좌표를  큐에 저장했고,

익지 않은 토마토의 경우 따로 3차원 배열 변수(cal_tomato)를 만들어서 해당 좌표에 대해 -1 상태로 저장했다.

 

그리고 BFS 알고리즘을 이용하는데 다음에 이동할 좌표를 계산하였을 때

다음 좌표가 0보다 작거나 입력받은 값보다 같거나 클 때, 그리고 토마토가 들어 있지 않거나, 이미 익은 토마토가 있는 좌표는 이동하면 안된다.

 

위 조건을 제외하고는 다음 좌표로 이동할 수 있고, (다음 좌표로 이동할 수 있다는 뜻이 익은 토마토가 된다는 뜻)

다음 좌표의 토마토가 익었다는 표시를 3차원 배열 변수(cal_tomato)에 몇일이 걸렸는지 저장하면 된다.

(다음 좌표 토마토 걸린 일수 = 현재 좌표 토마토 걸린 일 수 + 1)

그리고 큐에 익은 토마토의 좌표를 넣는다.

 

위 과정을 큐가 빌 때까지 반복한다.

 

그리고 마지막으로 익지 않은 토마토가 있는지 확인과 최소 일수를 구해야한다.

그래서 3차원 배열 변수(cal_tomato)에 -1이 남아있다면 익지 않은 토마토가 있다는 뜻이기 때문에 -1을 출력하고 종료한다.

그게 아니라면 max 함수를 이용하여 최소 일수를 찾고 마지막에 해당 값을 출력하고 종료하면 된다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

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

// 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 6방향

int tomato[101][101][101];
int cal_tomato[101][101][101] = { 0, };

int dh[6] = { 1, -1, 0, 0, 0, 0};
int dn[6] = { 0, 0, 0, 0, 1, -1};
int dm[6] = { 0, 0, -1, 1,0, 0};

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int M, N, H; // 가로칸의수, 세로칸의수, 상자의 수
    cin >> M >> N >> H;
    bool allnotsave = false;
    queue<pair<int, int>> hn;
    queue<int> m;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k < M; ++k) {
                cin >> tomato[i][j][k];// 1 : 익은 토마토, 0 : 익지 않은 토마토, -1 토마토가 들어 있지 않음

                if (tomato[i][j][k] == 0) {
                    // 익지 않은 토마토
                    allnotsave = true;
                    cal_tomato[i][j][k] = -1;
                }

                if (tomato[i][j][k] == 1) {
                    // 익은 토마토 좌표 저장
                    hn.push({ i, j });
                    m.push(k);
                }
            }
        }
    }

    if (!allnotsave) {
        // 저장될 때 모든 토마토가 익어있는 상태
        cout << 0;
        return 0;
    }

    while (!hn.empty() && !m.empty()) {
        pair<int, int> curhn = hn.front();
        int curm = m.front();
        hn.pop();
        m.pop();
        for (int i = 0; i < 6; ++i) {
            int nh = curhn.first + dh[i];
            int nn = curhn.second + dn[i];
            int nm = curm + dm[i];
            if (nh < 0 || nh >= H || nn < 0 || nn >= N || nm < 0 || nm >= M) continue;
            if (tomato[nh][nn][nm] == -1) continue; // 토마토 들어있지 않음 제외
            if (cal_tomato[nh][nn][nm] != -1)  continue; // 익은 토마토 제외
            cal_tomato[nh][nn][nm] = cal_tomato[curhn.first][curhn.second][curm] + 1; // 토마토 익었음
            hn.push({ nh,nn });
            m.push(nm);
        }
    }

    int result = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k < M; ++k) {
                if (cal_tomato[i][j][k] == -1) {
                    // 익지 않은 토마토가 있다면
                    cout << -1;
                    return 0;
                }
                result = max(result, cal_tomato[i][j][k]);
            }
        }
    }

    cout << result;

    return 0;
}