n개의 노드가 0부터 n-1까지 번호로 매겨져 있고, 무방향 간선(undirected edges)의 목록이 함께 주어졌다고 가정해 봅시다. 이때 그래프 내부에 존재하는 연결 요소(connected component)의 개수를 구하는 함수를 정의하는 것이 문제의 목표입니다.
예를 들어 n = 5이고 edges = [[0, 1], [1, 2], [3, 4]]인 경우를 살펴보겠습니다.
위 그래프에서 노드 0, 1, 2는 서로 연결되어 하나의 그룹을 이루고, 노드 3과 4는 별도의 그룹을 이룹니다. 따라서 연결 요소의 개수는 2가 됩니다.
문제 해결 접근 방법
이 문제는 DFS(깊이 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. 아직 방문하지 않은 노드를 발견할 때마다 DFS를 수행하여 해당 노드와 연결된 모든 노드를 방문 처리하고, 새로운 탐색이 시작될 때마다 카운트를 1씩 증가시키면 됩니다.
구체적인 알고리즘은 다음과 같습니다.
- dfs() 함수를 정의합니다. 이 함수는 node, graph, visited 배열을 매개변수로 받습니다.
- visited[node]가 false라면 visited[node]를 true로 설정합니다.
- i를 0부터 graph[node]의 크기보다 작을 때까지 1씩 증가시키며 반복합니다.
- dfs(graph[node][i], graph, visited)를 호출하여 인접한 노드를 재귀적으로 탐색합니다.
- 메인 로직에서는 다음을 수행합니다.
- 크기가 n인 visited 배열을 선언합니다.
- n이 0이라면 0을 반환합니다.
- edges를 순회하며 인접 리스트 형태의 graph 배열을 구성합니다.
- u := edges[i][0], v := edges[i][1]
- graph[u]의 끝에 v를 추가하고, graph[v]의 끝에 u를 추가합니다(무방향이므로 양쪽 모두 저장).
- ret := 0으로 초기화한 뒤, i를 0부터 n-1까지 반복합니다.
- visited[i]가 false라면 dfs(i, graph, visited)를 호출하고 ret을 1 증가시킵니다.
- 최종적으로 ret을 반환합니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void dfs(int node, vector<int> graph[], vector<bool>& visited){
if(visited[node]) return;
visited[node] = true;
for(int i = 0; i < graph[node].size(); i++){
dfs(graph[node][i], graph, visited);
}
}
int countComponents(int n, vector<vector<int>>& edges) {
if(!n) return 0;
vector<bool> visited(n);
vector<int> graph[n];
for(int i = 0; i < edges.size(); i++){
int u = edges[i][0];
int v = edges[i][1];
graph[u].push_back(v);
graph[v].push_back(u);
}
int ret = 0;
for(int i = 0; i < n; i++){
if(!visited[i]){
dfs(i, graph, visited);
ret++;
}
}
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,1},{1,2},{3,4}};
cout << (ob.countComponents(5, v));
}입력
5, [[0,1],[1,2],[3,4]]
출력
2
복잡도 분석
이 알고리즘의 시간 복잡도는 모든 노드와 간선을 한 번씩만 탐색하므로 O(n + e)(e는 간선의 개수)입니다. 공간 복잡도 역시 인접 리스트와 방문 배열을 저장해야 하므로 O(n + e)입니다.