[백준 C++] 7576, 7569번 토마토, 토마토

토마토

토마토

두 문제 모두 BFS를 활용해서 풀 수 있기 때문에 이번 기회에 BFS를 연습했다. 

비슷한 아이디어로 풀 수 있는 문제들이다. 두 문제 모두 상자에 있는 모든 토마토가 익는데 며칠 걸리는지 알아내는 문제다. 첫 번째 토마토 문제의 경우에는 상자가 하나 밖에 없으므로 상자의 가로, 세로 사이즈만 알면 풀 수 있지만, 두 번째 토마토 문제는 상자가 여러 개 있을 수 있기 때문에 가로, 세로 뿐만 아니라 높이도 알아야 한다. 그래서 조금 더 복잡하고 실수하기 쉽다.

두 문제의 공통적인 접근법은 다음과 같다.

1. 가로(M), 세로(N), 높이(H)는 int 타입으로 할당해 입력받는다. 하지만 칸 안에 토마토가 익었는지(1), 익지 않았는지(0), 아예 토마토가 없는지(-1)에 대한 정보는  int에 넣기에 메모리가 아깝다고 생각해 bool 타입에 넣었다. -1이라면 array에 true를 넣고, 0이라면 false를 넣으며, 1인 경우에만 queue에 넣고 array에 true를 넣는다. 아래가 두 번째 토마토 문제에서 array에 값을 넣는 코드다.

if (cell == -1) arr[i][j][k] = true;
else if (cell == 0) {
    arr[i][j][k] = false;
    chk2 = false;
} else {
    arr[i][j][k] = true;
    qu.push(st{0,i,j,k});
}

2. queue에는 익은 토마토가 들어있다. queue의 가장 오래된 토마토를 빼고(pop), 그 토마토가 영향을 미치는 토마토들을 queue에 넣는다. 첫 번째 토마토 문제에서는 동, 서, 남, 북, 두 번째 토마토 문제에서는 동, 서, 남, 북, 위, 아래다. 또한 queue에는 방향 정보 말고도 며칠이 지났는지에 대한 것(day)도 들어가 있다. day의 최대값은 ret라는 변수에 저장한다. 토마토를 넣을 때 넣었다고 체크를 해줘야 반복해서 같은 칸에 있는 토마토를 확인하지 않는다는 것을 주의하자. queue가 빌 때 까지 같은 작업을 반복한다.

3. 작업을 마치고 모든 토마토들이 익었다면 array를 탐색했을 때 모두 true가 나와야 한다. true가 나왔다면 2번 과정에서 구했던 day의 최대값을 출력하고, false가 나왔다면 익지 않은 토마토가 있다는 것이므로 -1을 출력한다.

첫 번째 토마토 문제의 소스코드다.

#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
#define FOR(i, N) for (int i = 0; i < N; i++)
#define LOCATE(Y, X) Y>=0&&X>=0&&Y<N&&X<M
bool arr[1000][1000];
int dirX[4] = {1, 0, -1, 0};
int dirY[4] = {0, 1, 0, -1};
queue<pair<int, pair<int, int>>> qu;
int M, N, cell, ret = 0;
void bfs() {
  while (!qu.empty()) {
    int y = qu.front().second.first;
    int x = qu.front().second.second;
    int day = qu.front().first;
    qu.pop();
    FOR(i, 4) {
      int newX = x + dirX[i];
      int newY = y + dirY[i];
      if (LOCATE(newY, newX) && !arr[newY][newX]) {
        qu.push(make_pair(day + 1, make_pair(newY, newX)));
        arr[newY][newX] = true;
        ret = max(ret, day + 1);
      }
    }
  }
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  bool chk = true;
  cin >> M >> N;
  FOR(i, N) {
    FOR(j, M) {
      cin >> cell;
      if (cell == -1) arr[i][j] = true;
      else if (cell == 0) arr[i][j] = false;
      else {
        arr[i][j] = true;
        qu.push(make_pair(0, make_pair(i, j)));
      }
    }
  }
  bfs();
  FOR(i, N) {
    FOR(j, M) {
      if (!arr[i][j]) {
        chk = false;
        break;
      }
    }
    if (!chk) break;
  }
  cout << ((!chk) ? -1 : ret) << '\n';
}

몇 가지 고생을 했던 포인트가 있어서 짚고 넘어가려고 한다.

• 박스를 벗어나는 것에 대해 제대로 처리해줘야 한다.`LOCATE(Y, X) Y>=0&&X>=0&&Y<N&&X<M` 이 부분을 작성할 때 실수로 Y > 0과 X > 0으로 해서 찾지도 못하고 애먹었다.
• bfs를 사용할 때는 queue에 넣을 때 넣었다는 표시를 해줘야 한다. queue에서 뺄 때 표시했다가 메모리 초과를 받았었다.

두 번째 토마토 문제의 소스코드다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define FOR(i, N) for (int i = 0; i < N; i++)
#define LOCATE(Y, X, Z) Y>=0&&X>=0&&Z>=0&&Y<N&&X<M&&Z<H
bool arr[100][100][100];
int dirX[6] = {1, 0, -1, 0, 0, 0};
int dirY[6] = {0, 1, 0, -1, 0, 0};
int dirZ[6] = {0, 0, 0, 0, 1, -1};
struct st
{
    int day,z,y,x;
};
queue<st> qu; // day, H, N, M
int M, N, H, cell, ret = 0;
void bfs() {
  while (!qu.empty()) {
    int y = qu.front().y;
    int x = qu.front().x;
    int z = qu.front().z;
    int day = qu.front().day;
    qu.pop();
    FOR(i, 6) {
      int newX = x + dirX[i];
      int newY = y + dirY[i];
      int newZ = z + dirZ[i];
      if (LOCATE(newY, newX, newZ) && !arr[newZ][newY][newX]) {
        qu.push(st{day + 1, newZ, newY, newX});
        arr[newZ][newY][newX] = true;
        ret = max(ret, day + 1);
      }
    }
  }
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  bool chk = true, chk2 = true;
  cin >> M >> N >> H;
  FOR(i, H) {
    FOR(j, N) {
      FOR(k, M) {
        cin >> cell;
        if (cell == -1) arr[i][j][k] = true;
        else if (cell == 0) {
          arr[i][j][k] = false;
          chk2 = false;
        }
        else {
          arr[i][j][k] = true;
          qu.push(st{0,i,j,k});
        }
      }
    }
  }
  if (chk2) {
    cout << 0 << '\n';
    return 0;
  }
  bfs();
  FOR(i, H) {
    FOR(j, N) {
      FOR(k, M) {
        if (!arr[i][j][k]) {
          chk = false;
          break;
        }
      }
      if (!chk) break;
    }
    if (!chk) break;
  }
  cout << ((!chk) ? -1 : ret) << '\n';
}

앞 문제와 거의 같다.

• 박스가 여러개 있는 상황이므로 좌표축이 하나 추가되어야 했다. 또한 x, y, day만 표현하면 됐을 때는 어떻게든 pair를 사용해서 해결했지만 이제는 x, y, z, day를 넣어야 하므로 struct를 하나 만들어서 queue의 자료형으로 사용했다. 어째서인지 arr[4]를 사용하니 안됐다.
• struct를 초기화하는 방법을 까먹을 뻔 했는데 이번 기회에 다시 기억했다. st{1,2,3,4}
• 소스코드가 이렇게 복잡하다 보니 디버깅 하던 것을 그대로 제출하는 실수를 했는데 그렇게 하면 출력 형식이 잘못되었다는 에러가 뜬다.