[백준] 11724 연결요소의 개수 C++ (BFS, DFS)

📌백준 11724 연결요소의 개수
https://www.acmicpc.net/problem/11724

그래프가 다 이어질 수도 있고 중간에 끊길 수도 있다.
이어지다가 끊기면 하나의 연결요소가 되는 것이다.
이 연결요소가 몇 개 있는지를 출력하는 문제이다.

DFS 함수는 연결된 요소들이 있으면 연속해서 호출된다. 그리고 더 이상 방문기록 없는 연결된 요소가 없으면 끝난다. 이어지다가 끊긴 것으로, 연결 요소 하나가 만들어졌다. 그리고 main()으로 돌아오는데, main()에서 인접리스트 요소 중 방문기록이 없으면 또 실행한다.
즉 main()에서 DFS를 실행할 때 연결요소 개수가 +1 되는 것이다.

BFS 함수는 큐가 빌 때까지 탐색한다. 즉 연결된 노드들을 탐색하고 끝나는 것이다. 이것도 DFS와 마찬가지로 더 이상 방문기록 없는 연결된 요소가 없으면 끝이나서 main()으로 돌아온다. 이때도 main()에서 BFS를 실행해줄 때 연결요소 개수가 +1 되는 것이다.

DFS 풀이

#include <iostream>
#include <vector>
using namespace std;

vector<int> vect[1001]; //인접리스트
int visited[1001];      //방문기록
int N, M;

/* DFS : 방문기록 남기는 용도 */
void DFS(int vertex)
{
    visited[vertex] = 1;
    for (int i = 0; i < vect[vertex].size(); i++) //최댓값 주의 : 벡터 그 원소에 해당하는 크기만큼 돌아야함
    {
        int idx = vect[vertex][i];
        if (visited[idx] == 0)
        {
            DFS(idx);
        }
    }
}

int main()
{
    int u, v;
    int cnt = 0;
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        cin >> u >> v;
        vect[u].push_back(v);
        vect[v].push_back(u); //무방향 그래프이기 때문
    }

    for (int i = 1; i <= N; i++) //빠짐없이 탐색하기 위해
    {
        if (visited[i] == 0)
        {
            cnt++;
            DFS(i);
        }
    }
    cout << cnt << "\n";
}

BFS 풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> vect[1001];
int visited[1001];
int N, M;

void BFS(int start)
{
    queue<int> q;
    q.push(start);
    visited[start] = 1;

    while (q.size() != 0)
    {
        // start가 아닌 가장 앞의 값에 인근 정점을 push 해줘야함
        int current = q.front();
        q.pop();
        for (int i = 0; i < vect[current].size(); i++)
        {
            if (visited[vect[current][i]] == 0)
            {
                visited[vect[current][i]] = 1; 
                q.push(vect[current][i]);
                //BFS는 재귀가 아니라서 큐에 push 해주는 동시에 방문기록 남겨야함.
            }
        }
    }
}

int main()
{
    int cnt = 0; //연결요소 개수 세는 변수
    int u, v;
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        cin >> u >> v;
        vect[u].push_back(v);
        vect[v].push_back(u);
    }

    //빠짐없이 탐색하기 위해
    for (int i = 1; i <= N; i++)
    {
        if (visited[i] == 0)
        {
            BFS(i);
            cnt++;
        }
    }
    cout << cnt;
}