[BOJ][실1][7576] 토마토

문제 링크

문제링크

첫 번째 풀이 : BFS

알고리즘

가장 기본적인 BFS를 진행합니다. 그리고 dp를 사용합니다.

• dp[x][y] : 현재까지 오는데 걸린 칸의 수
• dp[nx][ny] = dp[x][y]+1

두 가지가 핵심입니다.

1. BFS를 시작할 때 모든 익은 토마토를 q에 넣고 시작해야 합니다.
2. int sz = q.size()를 사용해서 BFS의 깊이를 측정하는 것이 포인트입니다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int MAX = 1001;

int arr[MAX][MAX];
int dp[MAX][MAX];
bool visited[MAX][MAX];

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

int n, m;
queue<pii> q;
int cnt = 0;

void show(void);
int bfs(int x, int y);

int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> m >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> arr[i][j];
      if (arr[i][j] == 1) {
        visited[i][j] = true;
        q.push(make_pair(i, j));
      }
      else if(arr[i][j] == 0) {
        cnt++;
      }
    }
  }
  cout << bfs(0, 0) << '\n';
  return 0;
}

void show(void) {
  cout << "============show========\n";
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cout << arr[i][j] << " ";
    }
    cout << "\n";
  }
  cout << "========================\n";
}

int bfs(int x, int y) {
  int nx, ny = 0;
  int days = -1;
  while (!q.empty()) {
    int sz = q.size();
    while (sz--) {
      pii curr = q.front();
      q.pop();
      for (int k = 0; k < 4; k++) {
        nx = curr.first + dx[k];
        ny = curr.second + dy[k];
        if (nx < 0 || nx >= n) continue;
        if (ny < 0 || ny >= m) continue;
        if (arr[nx][ny] == 0 && !visited[nx][ny]) {
          visited[nx][ny] = true;
          arr[nx][ny] = arr[curr.first][curr.second] + 1;
          cnt--;
          q.push(make_pair(nx, ny));
        }
      }
    }
    days++;
  }
  return cnt > 0 ? -1 : days;
}

Success Notice: 수고하셨습니다.