(1012) 유기농 배추

https://www.acmicpc.net/problem/1012

단계별로 풀어보기

27단계(그래프와 순회) 8번째

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int solve(){
  int m, n, k;
  
  cin >> m >> n >> k;
  
  vector v(n, vector<bool> (m));
  
  while(k--){
    int x, y;
    
    cin >> x >> y;
    
    v[y][x]= true;
  }
  
  int cnt= 0;
  
  auto dfs= [&](auto self, int nowx, int nowy) -> void {
    v[nowx][nowy]= false;
    
    for(int i=0;i<4;i++){
      int nextx= nowx+"0121"[i]-'1';
      int nexty= nowy+"1012"[i]-'1';
      
      if(nextx<0 || nextx>n-1 || nexty<0 || nexty>m-1)  continue;
      if(!v[nextx][nexty])  continue;
      
      self(self, nextx, nexty);
    }
  };
  
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(!v[i][j])  continue;
      
      cnt++;
      dfs(dfs, i, j);
    }
  }
  
  return cnt;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    cout << solve() << "\n";
  }
  
  return 0;
}