백준 1012 유기농 배추 (C++)

1012번: 유기농 배추

bfs를 이용한 문제이다. 배추가 심어져 있는 위치를 check에 true로 저장을 해주고 밭의 크기만큼 반복문을 돌면서 현재 위치가 true 일 경우 bfs를 돌려준다. bfs를 통해 true를 모두 false로 바꿔주고 이를 반복하며 카운트해준다. 최종적으로 인접해있는 배추들의 모음 개수를 카운트하게 되고 이를 출력해주었따. 간단하게 풀 수 있었던 문제였다.

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

using namespace std;

int T, M, N, K;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
bool check[50][50];

void bfs(int a, int b) {
    queue<pair<int, int>> q;

    q.push({ a, b });
    check[a][b] = false;

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
            if (!check[ny][nx]) continue;

            q.push({ ny,nx });
            check[ny][nx] = false;
        }
    }
}

void solution() {
    int result = 0;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (check[i][j]) {
                bfs(i, j);
                result++;
            }
        }
    }

    cout << result << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> T;

    while (T--) {
        cin >> M >> N >> K;

        int X, Y;
        for (int i = 0; i < K; i++) {
            cin >> X >> Y;
            check[Y][X] = true;
        }

        solution();

        memset(check, false, sizeof(check));
    }

    return 0;
}