11724번 연결 요소의 개수 | DFS, BFS | Baekjoon BOJ 백준 11724 C++ 코드, 해설, 풀이

 

 

 

이번 포스팅은 백준 11724번 연결 요소의 개수입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

 

 

기본 알고리즘

DFS 깊이우선탐색

BFS 너비우선탐색

 

 

 

전체 코드

 

DFS 깊이우선탐색

 

//백준11724 연결요소의개수
 
#include <iostream>
using namespace std;
 
const int MAX = 1001;
int N, M;
int map[MAX][MAX] = { 0, };
bool visited[MAX] = { 0, };
 
void DFS(int v) {
    visited[v] = true;
 
    for (int i = 1; i <= N; i++) {
        if (map[v][i] == 1 && visited[i] == 0) {
            visited[i] = 1;
            DFS(i);
        }
    }
}
 
int main() {
    cin >> N >> M;
 
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        map[u][v] = 1;
        map[v][u] = 1;
    }
 
    int cnt = 0;
    for (int i = 1; i <= N; i++) {
        if (visited[i] == 0) {
            DFS(i);
            cnt++;
        }
    }
 
    cout << cnt << endl;
}

 

 

 

---

 

BFS 너비우선탐색

 

//백준11724 연결요소의개수
 
#include <iostream>
#include <queue>
using namespace std;
 
const int MAX = 1001;
int N, M;
int map[MAX][MAX] = { 0, };
bool visited[MAX] = { 0, };
queue<int> q;
 
void BFS(int v) {
    q.push(v);
    visited[v] = true;
 
    while (!q.empty()) {
        v = q.front();
        q.pop();
 
        for (int i = 1; i <= N; i++) {
            if (map[v][i] == 1 && visited[i] == 0) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
}
 
int main() {
    cin >> N >> M;
 
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        map[u][v] = 1;
        map[v][u] = 1;
    }
 
    int cnt = 0;
    for (int i = 1; i <= N; i++) {
        if (visited[i] == 0) {
            BFS(i);
            cnt++;
        }
    }
 
    cout << cnt << endl;
}