백준 알고리즘 11724번 : 연결 요소의 개수

링크

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

sol1) DFS 컴포넌트 갯수 구하기

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int int64_t
using namespace std;

int vist[1001];
vector<int> adj[1001];

void dfs(int cur){
  vist[cur] = true;
  for(auto nxt : adj[cur]){
    if(vist[nxt]) continue;
    vist[nxt] = true;
    dfs(nxt);
  }
}

int32_t main() {
  fastio;
  int n,m,components = 0; cin >> n >> m;
  for(int i = 0; i < m; i++){
    int a,b; cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  for(int i = 1; i <= n; i++){
    if(!vist[i]){
      dfs(i);
      components++;
    }
  }
  cout << components << "\n";
}

풀이

DFS방식으로 풀었다(알고있는 그래프 탐색방법이 그것 밖에 없긴하지만...).
DFS는 연결요소가 아니면 탐색하지 못하기 때문에 이 문제에서 핵심이었던 부분은 main함수 안에서 2번째 반복문 부분이다.
1부터 정점의 갯수까지 반복하면서 방문하지 않은 정점이 있을 경우 dfs를 실행하고 components를 1증가시킨다.
저 부분을 몰라서 어쩔 수 없이 풀이를 보고 풀었다(...)

복기

DFS가 익숙하지 않아서 그냥 DFS탐색 틀만 짜놓고 고민을 계속해 보았지만 스스로 풀지 못했다.
이런 현상이 언제 좋아질지 모르겠지만 그냥 꾸준히 하는 수 밖에 없을 것 같다..