백준 7576(토마토) 풀이

문제

입력

출력

 

해결방법

 

#include <iostream>
#include <queue>

using namespace std;

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  int a[1000][1000];
  int vis[1000][1000] = {
      0,
  };
  queue<pair<int, int>> q;
  int x[4] = {-1, 0, 1, 0};
  int y[4] = {0, -1, 0, 1};
  int day = 0;

  cin >> m >> n;

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      cin >> a[i][j];
      if (a[i][j] == 1)
      {
        q.push({i, j});
      }
    }
  }

  while (!q.empty())
  {
    pair<int, int> tmp = q.front();
    q.pop();
    for (int k = 0; k < 4; k++)
    {
      int tmpx = tmp.first + x[k];
      int tmpy = tmp.second + y[k];
      int cnt = vis[tmp.first][tmp.second];

      if (tmpx < 0 || tmpy < 0 || tmpx > n - 1 || tmpy > m - 1)
      {
        continue;
      }

      if (vis[tmpx][tmpy] <= cnt + 1 && vis[tmpx][tmpy] != 0 || a[tmpx][tmpy] == 1 || a[tmpx][tmpy] == -1)
      {
        continue;
      }

      q.push({tmpx, tmpy});
      vis[tmpx][tmpy] = cnt + 1;
    }
  }

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      if (a[i][j] == 0 && vis[i][j] == 0)
      {
        cout << -1;
        return 0;
      }
      if (day < vis[i][j])
      {
        day = vis[i][j];
      }
    }
  }

  cout << day;
}

 

이 문제는 bfs로 해결할 수 있다.

vis배열은 토마토가 몇번째로 익는지 일수를 기록하기 위해 사용할 것이다.

처음으로 입력을 받고 입력을 받을 때 시작점이 될 수 있는 익은 토마토를 입력받으면 큐에 삽입한다.

 

시작점들을 큐에 모두 삽입했으므로 bfs를 실행한다.

이웃된 익은 토마토가 있을 때만 토마토가 익을 수 있기 때문에 익은 토마토에서 시작을 하고

그 주변의 안익은 토마토를 찾아간다.

안익은 토마토를 찾아갈 때 비어있거나 이미 익은 토마토는 피한다.

bfs를 돌릴 때 익은 토마토를 만났을 때는 더 빨리 익을 수 있으면 vis배열의 일수를 더 작은 일수로 교체해준다.

 

이렇게 모두 bfs를 실행한 후 모든 토마토를 확인해

안익은 토마토가 있으면 -1을 출력하고

모든 토마토가 익었으면 가장 늦게 익은 토마토의 일수를 출력한다.