[C++] 백준 BOJ 11724 연결 요소의 개수

문제 링크 : https://boj.kr/11724

문제의 컨셉은 간단하다.

주어진 그래프에서 하나로 이어져 있는 연결 요소의 개수를 찾는 문제로 위 그림에서 하나로 이어져있는 연결 요소 수는 2개가 된다.

입력의 경우는 미리 인접 리스트를 만들어 간선을 입력 받는다.

그 이후 1부터 N까지 DFS를 돌려서 DFS가 끝나는 시점에 카운트를 하나 증가시켜 주면서 다음 시작 요소로 DFS를 돌리는 식으로 반복하면 답을 구할 수 있다.

스택으로 구현한 방법이 함수를 사용하여 재귀로 돌리는 것보다 시간이 덜 걸릴 줄 알았는데 함수로 재귀 돌리는 것이 의미 없는 수치이긴 하지만 더 빨랐다.

(위 - 스택, 아래 - 재귀)

스택으로 구현한 방법

// BOJ 11724 연결 요소의 개수
#include <bits/stdc++.h>
 
using namespace std;
vector<int> node[1001];
bool visited[1001];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
 
    int num, edge;
    cin >> num >> edge;
    int s, e; // 시작점, 끝점
    // 가중치 없는 그래프 입력
    for(int i = 1; i <= edge; i++){
        cin >> s >> e;
        node[s].push_back(e);
        node[e].push_back(s);
    }
    stack<int> dfs;
    int cnt = 0;
    for(int i = 1; i <= num; i++) {
        // 방문하지 않은 시작점 수 == 연결요소의 갯수
        if(!visited[i]) {
            visited[i] = true;
            dfs.push(i);
            cnt++;
        }
        while (!dfs.empty()) {
            int cur = dfs.top();
            dfs.pop();
            for(int j = 0; j < node[cur].size(); j++){
                if(!visited[node[cur][j]]){
                    dfs.push(node[cur][j]);
                    visited[node[cur][j]] = true;
                }
            }
 
        }
    }
    cout << cnt;
    return 0;
}

재귀로 구현한 방법

// BOJ 11724 연결 요소의 개수
#include <bits/stdc++.h>
 
using namespace std;
vector<int> node[1001];
bool visited[1001];
 
void dfs(int input){
    if (!visited[input]) {
        visited[input] = true;
        for(int j = 0; j < node[input].size(); j++)
            dfs(node[input][j]);
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
 
    int num, edge;
    cin >> num >> edge;
    int s, e; // 시작점, 끝점
    // 가중치 없는 그래프 입력
    for(int i = 1; i <= edge; i++){
        cin >> s >> e;
        node[s].push_back(e);
        node[e].push_back(s);
    }
    int cnt = 0;
    for(int i = 1; i <= num; i++) {
        // 방문하지 않은 시작점 수 == 연결요소의 갯수
        if(!visited[i]) {
            dfs(i);
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}