1012번 유기농 배추 - C++

✅️[문제]
https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

✅️[풀이]

BFS 문제!
단순히 BFS를 돌릴때 방문횟수가 없는 큐에 처음 넣을때 ans+=1을 해주면 되는 문제이다!

✅️[코드]

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

int arr[52][52];

bool vis[52][52];

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

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

int main() {

    ios::sync_with_stdio(0);

    cin.tie(0);

    

    int T;

    cin >> T;

    

    while(T--){

        int M,N,K;

        cin >> M >> N >> K;

        

        while(K--){

            int x, y;

            cin >> x >> y;

            arr[y][x] = 1;

        }

        queue<pair<int,int>> q;

        int ans = 0;

        for(int i=0; i<N; i++){

            for(int j=0; j<M; j++){

                if(arr[i][j] == 1 && vis[i][j] == 0){

                    q.push({i,j});

                    ans++;

                }

                while(!q.empty()){

                    pair<int,int> q2 = q.front(); q.pop();

                    for(int i=0; i<4; i++){

                        int x = q2.X + dx[i];

                        int y = q2.Y + dy[i];

                        

                        if(x<0 || x>=N || y<0 || y>= M) continue;

                        if(arr[x][y] != 1 || vis[x][y] == 1) continue;

                        

                        vis[x][y] = 1;

                        q.push({x,y});

                    }

                }

                

            }

        }

        cout << ans << '\n';

        memset(arr, 0, sizeof(arr));
        memset(vis, 0, sizeof(vis));

    }

}