(2667) 단지번호붙이기

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

단계별로 풀어보기

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

 

 

 

인접한 상하좌우를 탐색하는 2차원 그래프 문제에서 주로 사용하는 방식인데, 숫자로 구성된 적절한 문자열의 인덱스를 이용하면 손쉽게 다음 지점을 탐색할 수 있다. 따로 배열 등을 지정할 필요 없이 그래프 탐색 코드 내에서 해결할 수 있기 때문에 개인적으로 가독성도 더 좋다.

 

 

 

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector v(n, vector<bool> (n));
  
  for(int i=0;i<n;i++){
    string s;
    
    cin >> s;
    
    for(int j=0;j<n;j++)  v[i][j]= s[j]=='1';
  }
  
  int cnt;
  vector<int> res;
  
  auto dfs= [&](auto self, int nowx, int nowy) -> void {
    v[nowx][nowy]= false;
    cnt++;
    
    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>n-1)  continue;
      if(!v[nextx][nexty])  continue;
      
      self(self, nextx, nexty);
    }
  };
  
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(!v[i][j])  continue;
      
      cnt= 0;
      dfs(dfs, i, j);
      res.push_back(cnt);
    }
  }
  
  sort(res.begin(), res.end());
  
  cout << res.size() << "\n";
  for(int elem:res)  cout << elem << "\n";
  
  return 0;
}