C++로 포리스트(숲)에 포함된 트리 개수 구하기

포리스트(forest, 트리들의 집합)를 구성하는 정점들이 주어졌을 때, 해당 포리스트 안에 몇 개의 트리가 존재하는지 구하는 것이 목표입니다. 이 문제는 DFS(깊이 우선 탐색) 알고리즘을 활용하면 간단하게 해결할 수 있습니다.

예시

입력

edges = { { 1,3 }, {2,8}, {2,6}, {3,5}, {3,7}, {4,8} }

출력

Count of number of trees in a forest are: 3

설명

주어진 간선들로 연결된 컴포넌트는 총 3개이며, 각각 하나의 트리를 이룹니다.

접근 방법

그래프에 재귀적으로 DFS를 수행하는 방식을 사용합니다. 하나의 시작 정점에서 출발해 연결된 모든 노드를 방문 처리했다면, 그것은 하나의 트리가 완성되었다는 의미이므로 카운트를 1 증가시킵니다.

• 정점의 개수를 나타내는 정수 vertice를 선언합니다.

• 정점들을 저장하기 위해 vector<int> vec[vertice] 배열을 사용합니다.

• insert() 함수는 vec[]와 부모·자식 노드를 인자로 받아 두 노드 사이에 간선을 추가합니다.

• 간선은 vec[parent].push_back(child)와 vec[child].push_back(parent)로 양방향으로 등록합니다.

• recurred() 함수는 시작 정점 temp부터 그래프 전체에 DFS를 적용합니다.

• check[] 배열은 true/false 값으로 각 노드의 방문 여부를 기록합니다.

• for 루프로 vec[temp]의 인접 노드들을 순회하면서, 아직 방문하지 않은 노드(check[vec[temp][i]] == false)라면 recurred(vec[temp][i], vec, check)를 재귀 호출합니다.

• Trees_Forest() 함수는 인접 리스트 형태의 vec[]를 받아 포리스트 내 트리의 개수를 반환합니다.

• 초기 카운트는 0으로 설정하고, 방문 여부를 저장할 vector<bool> check(vertice, false)를 생성합니다.

• 모든 정점을 for 루프로 순회하면서, check[i]가 false인 경우 recurred(i, vec, check)로 DFS를 수행하고 count를 증가시킵니다.

• 모든 반복이 끝나면 count를 결과로 반환합니다.

구현 코드

#include<bits/stdc++.h>
using namespace std;
void insert(vector<int> vec[], int parent, int child){
    vec[parent].push_back(child);
    vec[child].push_back(parent);
}
void recurred(int temp, vector<int> vec[], vector<bool> &check){
    check[temp] = true;
    int size = vec[temp].size();
    for(int i = 0; i < size; i++){
        if (check[vec[temp][i]] == false){
            recurred(vec[temp][i], vec, check);
        }
    }
}
int Trees_Forest(vector<int> vec[], int vertice){
    int count = 0;
    vector<bool> check(vertice, false);
    for(int i = 0; i < vertice; i++){
        if(check[i] == false){
            recurred(i, vec, check);
            count++;
        }
    }
    return count;
}
int main(){
    int vertice = 9;
    vector<int> vec[vertice];
    insert(vec, 1, 3);
    insert(vec, 2, 8);
    insert(vec, 2, 6);
    insert(vec, 3, 5);
    insert(vec, 3, 7);
    insert(vec, 4, 8);
    cout<<"Count of number of trees in a forest are: "<<Trees_Forest(vec, vertice);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Count of number of trees in a forest are: 3

이 알고리즘의 시간 복잡도는 정점과 간선의 합에 비례하는 O(V + E)이며, 공간 복잡도 역시 O(V + E)입니다. DFS를 한 번씩만 수행하므로 대규모 그래프에서도 효율적으로 동작합니다.