Boj 1012 c++ 유기농 배추(feat: 연결 요소의 개수)

그래프 탐색은 재미있다. 모든 문제가 연결요소의 개수로 돌아온다. 문제를 풀 때 주의할 점: 테스트 케이스가 여러개일 때 배열 초기화 하기

 

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int T, M, N, K;
int arr[51][51];
int visited[51][51];
queue<pair<int, int>> q;

void BFS(int U, int V){

    visited[U][V]=1;
    int dx[4]={0, 0, 1, -1};
    int dy[4]={1, -1, 0, 0};
    q.push({U, V});
    while(!q.empty()){
        U=q.front().first;
        V=q.front().second;
        for(int i=0; i<4; i++){
            int nx=dx[i]+U;
            int ny=dy[i]+V;
            if(nx<0 || ny<0 || nx>=M || ny>=N)
                continue;
            if(arr[nx][ny]==1 && !visited[nx][ny]){
                visited[nx][ny]=1;
                q.push({nx, ny});
            }
        }q.pop();
    }
}

int main(){

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


  cin>>T;

  while(T--){
    cin>>M>>N>>K;
    for(int i=0; i<50; i++){
        for(int j=0; j<50; j++){
            arr[i][j]=0;
            visited[i][j]=0;
        }
    }
    while(K--){
        int u, v;
        cin>>u>>v;
        arr[u][v]=1;
    }
    int cnt=0;
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            if(arr[i][j]==1 && !visited[i][j]){
                BFS(i, j);
                cnt++;}
        }
    }
    cout<<cnt<<"\n";
  }



}