C++ 코딩테스트 강좌, 연결 요소의 개수 구하기

안녕하세요! 오늘은 C++ 코딩테스트에서 자주 등장하는 알고리즘 문제 중 하나인 “연결 요소의 개수 구하기”에 대해 알아보겠습니다. 이 문제는 그래프 이론에서 중요한 개념 중 하나인 ‘연결 요소’를 이해하고 구현하는 데 큰 도움이 될 것입니다.

문제 설명

주어진 무방향 그래프에서 연결 요소의 개수를 구하는 문제입니다. 연결 요소란 그래프의 부분 그래프 중에서 서로 연결된 정점들로 이루어진 집합을 의미합니다. 그래프의 정점들 사이에 간선이 있을 때, 직간접적으로 연결된 모든 정점들은 하나의 연결 요소로 간주됩니다. 예를 들어, 아래와 같은 그래프가 있다고 가정해 봅시다.

이 그래프는 1, 0, 2, 3이 연결된 하나의 연결 요소이며, 다음과 같은 독립된 정점이 있을 경우 연결 요소의 개수는 두 개가 됩니다.

그림과 같이 1, 2, 3이 포함된 연결 요소와 4가 포함된 연결 요소로 구분될 수 있습니다.

입력 형식

첫 번째 줄에는 정점의 개수 N (1 ≤ N ≤ 1000)과 간선의 개수 M (0 ≤ M ≤ N*(N-1)/2)이 주어진다.
다음 M개의 줄에 걸쳐 각 간선에 대한 정보를 나타내며, 두 개의 정점 A와 B가 주어진다. 이를 통해 정점 A와 B가 연결되어 있음을 나타냅니다.

출력 형식

연결 요소의 개수를 출력합니다.

예제

입력:
5 3
0 1
0 2
3 4

출력:
2

문제 풀이

이 문제를 해결하기 위해서는 다음과 같은 과정으로 접근합니다.

1. 그래프 표현

그래프를 표현하기 위해 인접 리스트(adjacency list)를 사용합니다. 각 정점에 대한 연결 정보를 저장하는 벡터를 선언하고, M개의 간선 정보를 입력받아 그래프를 구성합니다. C++ STL의 vector를 활용하여 쉽게 구현할 수 있습니다.

#include <iostream>
#include <vector>

using namespace std;

vector> graph;
void addEdge(int a, int b) {
    graph[a].push_back(b);
    graph[b].push_back(a);
}

2. DFS 또는 BFS 이용하기

연결 요소의 개수를 구하기 위해 그래프의 모든 정점을 탐색할 필요가 있습니다. 우리가 선택한 탐색 방법은 깊이 우선 탐색(DFS)입니다. 이를 통해 현재 탐색하는 정점과 연결된 모든 정점들을 방문하게 됩니다. 방문한 정점들은 미처리 상태에서 ‘방문’ 상태로 변경하여 중복 방문을 피합니다.

void dfs(int node, vector& visited) {
    visited[node] = true; // 현재 노드를 방문 상태로 변경
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited);
        }
    }
}

3. 주요 변수 및 로직 구현

연결 요소의 개수를 세기 위한 변수 components를 선언하고, 모든 정점을 차례대로 탐색합니다. 각 정점을 방문할 때마다 DFS를 호출하고, 호출 전에 components를 증가시킵니다. 이 단계에서 모든 정점을 확인하면 총 연결 요소의 개수를 알 수 있습니다.

int main() {
    int n, m;
    cin >> n >> m;

    graph.resize(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        addEdge(a, b);
    }

    vector visited(n, false);
    int components = 0;

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i, visited);
            components++; // 새로운 연결 요소 발견
        }
    }

    cout << components << endl; // 결과 출력
    return 0;
}

전체 코드

#include <iostream>
#include <vector>

using namespace std;

vector> graph;

// 간선 추가 함수
void addEdge(int a, int b) {
    graph[a].push_back(b);
    graph[b].push_back(a);
}

// DFS 함수
void dfs(int node, vector& visited) {
    visited[node] = true; // 현재 노드를 방문 상태로 변경
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    graph.resize(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        addEdge(a, b);
    }

    vector visited(n, false);
    int components = 0;

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i, visited);
            components++; // 새로운 연결 요소 발견
        }
    }

    cout << components << endl; // 결과 출력
    return 0;
}

알고리즘 복습

이제 이 문제를 통해 우리는 그래프를 표현하고, DFS를 통해 연결 요소를 탐색하는 방법을 배웠습니다. 알고리즘의 복잡도는 다음과 같습니다:

시간 복잡도: O(N + M), 여기서 N은 정점의 수, M은 간선의 수입니다.
공간 복잡도: O(N + M) 그래프를 저장하기 위한 공간과 방문 여부를 저장하기 위한 공간이 필요합니다.

문제 해결을 위한 팁

문제를 풀기 전에 그래프가 어떻게 구성되었는지 그림으로 그려보세요. 이를 통해 문제 이해가 더 쉬워집니다.
각 연결 요소를 찾을 때 BFS를 사용해도 좋습니다. BFS는 레벨 순서로 탐색하기 때문에 특정 문제에서 유리할 수 있습니다.
상황에 따라 연결 요소의 개수 외에도 각 요소의 크기 또는 구조를 분석하는 문제가 나올 수 있으니, 그래프 탐색을 익히는 것이 좋습니다.

여기까지가 “연결 요소의 개수 구하기” 문제 풀이였습니다. 이 강좌가 유익했기를 바라며, 앞으로 다양한 알고리즘과 문제들을 함께 살펴보겠습니다. 감사합니다!