baekjoon 2667:단지번호붙이기

baekjoon 2667 단지번호붙이기

2667번 단지번호 붙이기

접근

저번에 만들었던 dfsall 변형시키면 될 것 같다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void dfsall(vector<vector<int>>& graph, vector<vector<bool>>& visited, vector<int>& outcome);
int dfs(vector<vector<int>>& graph, vector<vector<bool>>& visited, int a, int b);
int main (){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin >> n;
  vector<vector<int>> graph(n, vector<int>(n, 0));
  vector<vector<bool>> visited(n, vector<bool>(n, false));
  for(int i = 0; i < n; i++){
    string s; cin >> s;
    for(int j = 0; j < n; j++){
      graph[i][j] = s[j] - '0';
    }
  }
  vector<int> outcome;
  dfsall(graph, visited, outcome);
  sort(outcome.begin(), outcome.end());
  cout << outcome.size() << "\n";
  for(int i = 0; i < outcome.size(); i++){
    cout << outcome[i] << "\n";
  }


  return 0;
}
void dfsall(vector<vector<int>>& graph, vector<vector<bool>>& visited, vector<int>& outcome){
  
  for(int i = 0; i < graph.size(); i++){
    for(int j = 0; j < graph[i].size(); j++){
      if(!visited[i][j] && graph[i][j] == 1){
        //(i, j)에서 탐색 시작해서 멈추면 count++
        outcome.push_back(dfs(graph, visited, i, j));
      }
    }
  }
}
int dfs(vector<vector<int>>& graph, vector<vector<bool>>& visited, int a, int b){
  visited[a][b] = true;
  //그냥 dfs와 다르게 이건 상하좌우로 탐색해야한다.
  int count = 1; //현재노드
  if(a+1 < graph.size() && graph[a+1][b] == 1 && visited[a+1][b] == false){
    count += dfs(graph, visited, a+1, b);
  }
  if(a-1 >= 0 && graph[a-1][b] == 1 && visited[a-1][b] == false){
    count += dfs(graph, visited, a-1, b);
  }
  if(b+1 < graph.size() && graph[a][b+1] == 1 && visited[a][b+1] == false){
    count += dfs(graph, visited, a, b+1);
  }
  if(b-1 >= 0 && graph[a][b-1] == 1 && visited[a][b-1] == false){
    count += dfs(graph, visited, a, b-1);
  }
  return count;
}

배운 점

없는 듯