[BOJ알고리즘, C++]#11724_연결 요소의 개수, 그래프, DFS, 깊이 우선 탐색

 

#1. 문제

11724번: 연결 요소의 개수

 

---

 

#2. 풀이

 

1. 그래프 탐색

[자료구조]#6_그래프

 

그래프의 모든 정점을 탐색하는 방법은 두 가지입니다. 하나는 DFS(깊이 우선 탐색), 그리고 다른 하나는 BFS(너비 우선 탐색)입니다. 각각 재귀/스택과 큐 자료구조를 활용해 구현가능합니다.

 

2. 무방향 그래프, 연결 요소? BFS 혹은 DFS를 활용하자

 

1. 무방향 그래프이며, 각 간선에 가중치가 존재하지 않습니다. 따라서, DFS 혹은 BFS를 활용하며, 각 정점에 대하여 양방향으로(출발 정점이 곧 도착 정점이 되는) 그래프를 구성해 줍니다.
2. 각 정점에 대하여 방문 여부를 체크하고 DFS를 수행해 줍니다. 한 번의 DFS를 수행하고 나면, 이 과정에서 방문한 정점들은 방문 여부가 체크되어 뒤 이어 수행하는 DFS 과정에서 해당 정점들에 대한 탐색을 생략하게 됩니다. 따라서, 각 정점에 대하여 DFS를 수행하고 카운트를 해주어, 연결 요소의 개수를 셉니다.

 

---

 

#3. 코드 : 재귀 DFS 활용

 

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

int N, M, ans;
vector<vector<int>> graph;
vector<bool> visited;

void dfs(int node)
{
    visited[node] = true;

    for (const auto next : graph[node])
    {
        if (!visited[next])
            dfs(next);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    graph.resize(N + 1);
    visited.resize(N + 1, false);

    while (M--)
    {
        int u, v;
        cin >> u >> v;

        // #1. 무방향 그래프, u 와 v 모두 시작 정점과 도착 정점이 될 수 있다.
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    for (int i = 1; i <= N; ++i)
    {
        if (!visited[i])
        {
            dfs(i);
            ans++;
        }
    }

    cout << ans;

    return 0;
}

 

---