BOJ 1012 유기농 배추

1 개요

BOJ 1012 유기농 배추

• 백준 온라인 저지 1012번 문제
• BOJ 31단계

2 C++

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

int T, M, N, K;
int X, Y, x, y;
bool A[51][51] = {};
bool visited[51][51] = {};
int cnt;

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

void bfs(int sx, int sy) {
    queue<pair<int,int>> q;
    q.push({sx, sy});
    visited[sx][sy] = true;
    int nx, ny;
    while(!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for(int i=0; i<4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            if(nx>=0 && nx<M && ny>=0 && ny<N && A[nx][ny] && !visited[nx][ny]) {
                q.push({nx, ny});
                visited[nx][ny] = true;
            }
        }
    }
}

void solve() {
    for(int x=0; x<M; x++) {
        for(int y=0; y<N; y++) {
            if(A[x][y] && !visited[x][y]) {
                bfs(x, y);
                cnt++;
            }
        }
    }
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d %d", &M, &N, &K);
        for(int x=0; x<M; x++) {
            for(int y=0; y<N; y++) {
                A[x][y] = false;
                visited[x][y] = false;
            }
        }
        for(int i=0; i<K; i++) {
            scanf("%d %d", &X, &Y);
            A[X][Y] = true;
    	}
    	cnt = 0;
        solve();    
        printf("%d\n", cnt);
    }
}