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

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

예전엔 bfs가 편해서 bfs로만 풀었었는데,,, ㅎㅅㅎ 나의 dfs 도전기... 앞으로 두가지 방식 모두로 풀어볼란다 후후

 

나! 다짐했어 (두둥)

오늘부터 dfs 마스터가 될꺼야!!!!! 응캬캬캬 🐮 

 

두 방식다 11724 문제에서는 같은 성격을 띠고 있지요 ㅎㅎ

 

dfs도 그렇고 bfs도 그렇고 한 노드에서 시작해서 이제 더이상 연결 되어 있지 않았다면 dfs는 dfs 함수가 더 이상 스택에 쌓이지 않을것이고, bfs는 queue에 들어가는 수가 없으니 while문이 멈출 것이다 ㅎㅎ

 

그렇기 때문에 1~노드의 개수 만큼 for문으로 vis vector을 확인하면서 방문하지 않은 node가 있는 경우 count를 해주는 것이다. ㅎㅎ

예를 들어 bfs(1)-> 1,2,5를 방문한다. 그러면 vis[1], vis[2], vis[5]는 방문 표시가 돼있을 것이다(true!!)

그러면 함수가 끝이나고 다시 for문으로 돌아가서 방문하지 않은 곳을 확인하고 다시 함수를 실행한다. 

현재는 3을 방문하지 않았으니 bfs(3)을 실행해서 3과 연결된 아이들을 확인하고 온다. 

 

그러면 전체적인 묶음의 개수를 확인할 수 있는 것이다. 

 

 DFS로 푼 방식 

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<bool> vis(1001, false);
vector<int> connection[1001];
void dfs(int v)
{
    vis[v] = true;
    for (int i = 0; i < connection[v].size(); i++) {
        int to = connection[v][i];
        if (!vis[to])
            dfs(to);
    }
}
int main()
{
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        connection[a].push_back(b);
        connection[b].push_back(a);
    }

    int answer = 0;

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            answer++;
            dfs(i);
        }
    }
    cout << answer << "\n";

    return 0;
}

 

 BFS로 푼 방식 

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

vector<int> connection[1001];
vector<bool> vis(1001, false);
void bfs(int v)
{
    queue<int> q;
    q.push(v);
    vis[v] = true;
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        for (int i = 0; i < connection[t].size(); i++) {
            int to = connection[t][i];
            if (!vis[to]) {
                vis[to] = true;
                q.push(to);
            }
        }
    }
}
int main()
{
    int n, m, answer = 0;
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        connection[a].push_back(b);
        connection[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            answer++;
            bfs(i);
        }
    }
    cout << answer << "\n";
    return 0;
}