[PS] 백준 1012번 - 유기농 배추

2667번 단자번호붙이기 문제와 비슷하게 BFS로 해결하였다.

#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

int T, N, M, K, a[50][50] = {};
int cnt[2500] = {};

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

void BFS(int c) {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      if (a[i][j] == 1) {
        queue<pair<int, int>> q;
        q.push({i, j});
        a[i][j] = 0;
        cnt[c]++;
        while (!q.empty()) {
          int x = q.front().first, y = q.front().second;
          q.pop();
          for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx >= 0 && nx < N && ny >= 0 && ny < M && a[nx][ny] == 1) {
              q.push({nx, ny});
              a[nx][ny] = 0;
            }
          }
        }
      }
    }
  }
}

int main(void) {
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> N >> M >> K;
        memset(a, 0, sizeof(a));
        for(int j = 0; j < K; j++) {
            int x, y;
            cin >> x >> y;
            a[x][y] = 1;
        }
        BFS(i);
    }
    for (int i = 0; i < T; i++) cout << cnt[i] << "\n";
}