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

문제링크 : https://www.acmicpc.net/problem/7569

백준에 보면 토마토 문제가 2개가 존재한다.

하나는 2차원 상의 토마토 문제이고

이번 문제는 3차원상에 존재하는 토마토상자에 대해서 문제를 풀어야 한다.

문제는 단순하게 BFS를 이용하면 풀리게 되며 3차원인것만 주의해서 풀어주면 된다.

이번문제는 다음과 같은 점을 유의하면서 풀어보자

① BFS 구현

② 토마토가 익어가는 방향

③ 결과에 따른 출력 값

1. BFS구현

모든 익은 토마토를 매회 차 마다 확인하면 매우 손해 기 때문에

이번 문제에서는 새로 익은 토마토를 기준으로 새로 익은 토마토만 확인해 나갈 것이다.

처음 입력을 받을때 익은 토마토를 넣고

익은 토마토가 다른 토마토를 익힐때

익게된 토마토만 다시 큐에 넣게 된다.

2. 토마토가 익어가는 방향

인접해 있는 토마토가 익어갈때 어떤 방향으로 가는지 잘 생각해보면

6개의 방향으로 가는것을 알 수 있다.

상 하 좌 우 위 아래

이렇게 6개에 해당하는 dy dx dz배열을 만들어서 돌려주면 편하게 익어간다.

3. 결과값에 따른 출력

우리가 얻게 될 결과는 총 3가지에 해당한다.

1. 익는데 걸린 시간

2. 저장될 때 부터 익어있는 상태

3. 토마토가 모두 익지 못하는 상황

결과를 확인하는 메소드에 다음과 같은 경우를 고려해서 결과를 확인하는 메소드를 만들자.

그렇게 작성한 코드는 다음과 같다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117

#include <iostream> #include <utility> #include <queue>   using namespace std;   struct point {     int x;     int y;     int z; };   int box[102][102][102] = {-1}; int leftTomato = 0; queue<point> checkPoint; int m, n, h; int dx[6] = {0, 0, 0, 0, 1, -1}; int dy[6] = {0, 0, 1, -1, 0, 0}; int dz[6] = {1, -1, 0, 0, 0, 0}; bool findAnswer = false; bool isChanged = false; int answer = 0;   // 입력을 받는 메소드 void getInput() {     for (int i = 0; i < h; i++) {         for (int j = 0; j < n; j++) {             for (int k = 0; k < m; k++) {                 int tmp;                 cin >> tmp;                 box[i][j][k] = tmp;                   // 남은 토마토의 개수를 새는 곳                 if (tmp == 0) {                     leftTomato++;                 }                   // 익은 토마토의 좌표를 넣는 곳                 if (tmp == 1) {                     point p;                     p.x = k;                     p.y = j;                     p.z = i;                     checkPoint.push(p);                 }               }         }     } }   void firstCheck() {     if (leftTomato == 0) {         findAnswer = true;     } }   void checkAnswer() {     if (leftTomato == 0) {         findAnswer = true;     } else {         if (!isChanged) {             findAnswer = true;             answer = -1;         } else {            isChanged = false;         }     } }   void checkPush(point newP) {     if (newP.x >= 0 & newP.y >= 0 & newP.z >= 0 & newP.x < m & newP.y < n & newP.z < h) {         if (box[newP.z][newP.y][newP.x] == 0) {             box[newP.z][newP.y][newP.x] = 1;             checkPoint.push(newP);             leftTomato--;             isChanged = true;         }     } }   void ripe(point p) {     for (int i = 0; i < 6; i++) {         point newP;         newP.x = p.x + dx[i];         newP.y = p.y + dy[i];         newP.z = p.z + dz[i];         checkPush(newP);     } }     void runTomato() {     int size = checkPoint.size();     firstCheck();     while (size > 0 & !findAnswer) {         for (int i = 0; i < size; i++) {             point p = checkPoint.front();             checkPoint.pop();             ripe(p);         }         answer++;         checkAnswer();         size = checkPoint.size();     } }     int main() {       cin >> m >> n >> h;     getInput();     runTomato();     cout << answer;     return 0; }   Colored by Color Scripter

cs