[C++] 백준 11724번 : 연결 요소의 개수 풀이

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

11724번: 연결 요소의 개수

이 문제는 방향이 없는 그래프를 주어졌을 때, 연결 요소의 개수를 구하는 문제이다. 즉 간선으로 연결되어 있는 집합의 개수가 총 몇 개인지를 출력하는 프로그램이다. bfs, dfs 모두 사용할 수 있는 문제지만 나는 dfs를 이용하였다. 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>

using namespace std;

bool visit[1001]; //방문 여부 판단
vector<int> g[1001]; //인접 리스트
void dfs(int n) { //DFS 함수
    visit[n] = 1;
    for(int nxt : g[n]) {
        if(!visit[nxt])
            dfs(nxt);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); //시간 감소
    int N, M; cin >> N >> M;
    for(int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); //비방향성 그래프이므로 인접 리스트에 u->v, v->u 모두 추가
        g[v].push_back(u);
    }
    int cnt = 0;
    for(int i = 1; i <= N; i++) { //1부터 N까지 dfs를 하며 연결 요소의 개수 카운트
        if(!visit[i]) { //방문하지 않은 번호에서만 dfs
            dfs(i);
            cnt++;
        }
    }
    cout << cnt;
}

이 문제는 가장 간단한 DFS 문제중 하나이다. 1번 노드부터 N번 노드까지 DFS를 이용해 전부 방문하고 나면 visit 배열을 통해 방문한 노드인지 확인할 수 있다. 그러므로 이미 방문한 DFS의 횟수를 통해 연결 요소의 개수를 셀 수 있다.

인접 행렬은 인접 리스트에 비해 많은 메모리를 소모하기 때문에 vector를 지원하는 C++에서는 인접 리스트를 사용하는 것이 굉장히 좋다. DFS에서 재귀를 이용해 탐색할 때 방문 여부를 언제 체크하냐에 따라 재귀의 횟수를 많이 줄일 수 있다. 위와 같이 재귀를 하기 전에 방문 여부를 확인할 경우가 있고 재귀를 들어가서 첫 줄에 방문했을 경우 return하는 방식으로 프로그램을 구현할 수 있다. 후자의 경우 불필요한 방문이 될 수 있으므로 위의 코드와 같이 전자 방식으로 구현하는 것이 더 효율적이다.