C++ 코딩테스트 강좌, DFS와 BFS 프로그램

본 글에서는 DFS(Depth First Search)와 BFS(Breadth First Search) 알고리즘을 이용한 C++ 코딩 테스트 문제를 해결하는 방법에 대해 설명하겠습니다. 각 알고리즘의 개념 및 특징, 구체적인 코드 예제와 이를 바탕으로 한 문제 풀이 과정을 단계별로 설명하도록 하겠습니다.

1. DFS(Depth First Search) 알고리즘

DFS는 그래프를 탐색하는 알고리즘 중 하나로, 깊이 우선 탐색이라고도 불립니다. 그래프의 한 정점에서 시작해 인접한 정점으로 계속해서 깊이 들어가면서 탐색을 진행합니다. 더 이상 깊이 들어갈 수 없게 되면, 마지막에 방문한 정점으로 돌아가서 다른 인접 정점을 탐색합니다.

1.1 DFS의 특징

스택을 이용한 구현 또는 재귀를 사용하여 쉽게 구현할 수 있습니다.
모든 정점을 한 번씩 방문하므로, 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 수, E는 간선의 수입니다.
실행 중 방문한 정점의 정보를 저장해야 하므로, 추가적인 메모리가 필요합니다.

1.2 DFS의 구현

                
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void DFS(int start, vector &visited, const vector> &adj) {
    stack s;
    s.push(start);

    while (!s.empty()) {
        int node = s.top();
        s.pop();

        if (!visited[node]) {
            visited[node] = true;
            cout << node << ' ';

            for (int i = adj[node].size() - 1; i >= 0; --i) {
                if (!visited[adj[node][i]]) {
                    s.push(adj[node][i]);
                }
            }
        }
    }
}

2. BFS(Breadth First Search) 알고리즘

BFS는 그래프를 탐색하는 알고리즘 중 하나로, 너비 우선 탐색이라고도 불립니다. 그래프의 한 정점에서 시작해 인접한 모든 정점을 먼저 방문한 후, 그 다음 깊이로 들어가며 탐색을 진행합니다.

2.1 BFS의 특징

큐를 이용하여 구현합니다.
모든 정점을 한 번씩 방문하므로, 시간 복잡도는 O(V + E)입니다.
최단 경로 탐색에 적합한 방법입니다.

2.2 BFS의 구현

                
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void BFS(int start, vector &visited, const vector> &adj) {
    queue q;
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << ' ';

        for (int i = 0; i < adj[node].size(); ++i) {
            if (!visited[adj[node][i]]) {
                visited[adj[node][i]] = true;
                q.push(adj[node][i]);
            }
        }
    }
}

3. 문제: 그래프 탐색 (DFS 및 BFS 응용)

문제 설명: 주어진 비연결 그래프에서 연결 요소의 개수를 구하는 프로그램을 작성하시오. 그래프의 정점과 간선이 주어질 때, DFS 및 BFS 알고리즘을 사용하여 연결된 정점의 집합을 탐색하여 연결 요소의 개수를 계산합니다.

3.1 입력 형식

첫째 줄에 정점의 수 N (1 <= N <= 1000)과 간선의 수 M (1 <= M <= 100,000)이 주어진다. 다음 M개의 줄에는 간선 정보가 주어진다.

3.2 출력 형식

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

3.3 예제

                
Input:
5 3
1 2
2 3
4 5

Output:
2

3.4 풀이 과정

이 문제는 DFS와 BFS 알고리즘을 함께 활용하여 연결 요소의 개수를 구할 수 있습니다.

그래프를 인접 리스트 형태로 표현합니다.
결방문 정점을 기록할 visited 배열을 초기화합니다.
정점을 하나씩 순회하며, 방문하지 않은 정점이 발견될 때마다 DFS 또는 BFS를 이용하여 그 정점이 포함된 모든 정점을 방문합니다.
연결 요소가 발견될 때마다 카운트를 증가시키고, 최종적으로 카운트를 출력합니다.

3.5 C++ 코드 예제

                
#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

void DFS(int start, vector &visited, const vector> &adj) {
    stack s;
    s.push(start);

    while (!s.empty()) {
        int node = s.top();
        s.pop();

        if (!visited[node]) {
            visited[node] = true;

            for (int i = 0; i < adj[node].size(); ++i) {
                if (!visited[adj[node][i]]) {
                    s.push(adj[node][i]);
                }
            }
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    vector> adj(N + 1);
    vector visited(N + 1, false);

    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); // 무향 그래프이므로 양 방향으로 추가합니다.
    }

    int componentCount = 0;

    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            DFS(i, visited, adj);
            componentCount++;
        }
    }

    cout << componentCount << endl;
    
    return 0;
}