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

Posted on | In

저번부터 계속 그래프 문제를 건드리고 있다. 연결 요소의 개수 문제는 내가 공부하는 피피티? 에 소개가 되어 있어서 한번 풀어 보았다. (링크) 계속 여기 있는 문제를 풀 거 같다. 문제 링크는 다음과 같다.

https://www.acmicpc.net/problem/11724

문제 설명

이 문제가 어떤 문제인지 간략히 설명하자면, 그래프가 다 연결이 되어 있는 연결 그래프(트리라고 하기도 하는 것 같다)가 아니라 어느 한 군데가 빵꾸가 난? 그래프를 말한다. 이 그래프에서, 연결된 sub-graph들이 몇개인지 세는 문제이다. 우리가 그래프 탐색을 진행하면, 연결 그래프에서만 모든 노드들을 흝을 수 있으므로 그래프 탐색을 진행하는 횟수가 연결 그래프의 갯수가 되고, 이것이 결국 연결 요소(Connected components)의 개수가 된다. 이 문제는 결국 그래프 탐색 그 자체에 무엇이 있는 게 아니라 그래프 탐색을 진행하는 횟수를 세는 게 관건이므로, dfs든 bfs든 어떤 그래프 탐색을 사용해도 상관이 없다. 따라서 나는 두 풀이 모두 설명하려고 한다!

전반적인 풀이

결국은 1번 노드부터 마지막 노드까지 그래프 탐색(either dfs/bfs)을 진행하면서 카운트하면 된다. 이때, 어떤 노드를 먼저 방문하던 그래프 탐색으로 하나의 연결된 subgraph의 노드는 모두 방문이 되므로 1번 노드부터 마지막 노드까지 탐색을 진행할 때 이미 방문된 노드라면 카운트하지 않으면 된다.(이전에 이미 그 subgraph는 카운트되었다.) 따라서 방문하지 않은 노드에 탐색을 진행할 때마다 cnt++해주면 된다.

dfs 풀이

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

int n,m;
vector<int> adj[1000000];
bool visit[1000000];

void dfs(int x){
    if(visit[x]) return; // 이미 방문한 노드라면 탐색 진행할 필요 없이 return

    visit[x]=true;
    for(int i=0;i<adj[x].size();i++){
        if(!visit[adj[x][i]]) dfs(adj[x][i]);
    }
}


int main(){
    int u, v;
    scanf("%d%d", &n, &m);
    for(int i=0;i<m;i++){
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u); // 방향이 없는 그래프
    }

    int cnt=0;
    for(int i=1;i<=n;i++){
        if(!visit[i]){ // 방문하지 않은 노드일 때만 cnt++
            dfs(i);
            cnt++;
        }
    }
    printf("%d\n", cnt);
}

탐색 진행 부분만 df를 활용한 것이다. 위에서 설명하였기 때문에 간단히 주석으로만 설명한다.

bfs 설명

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

int n,m;
vector<int> adj[1000000];
bool visit[1000000];


void bfs(int s){ // starting point 
    if(visit[s]) return;

    queue<int> q;
    q.push(s); // 시작 노드 q에 넣기
    visit[s]=true; // 방문처리

    while(!q.empty()){
        int x=q.front(); // 맨 앞에껄 뽑으면서 
        q.pop();

        for(int i=0;i<adj[x].size();i++){ // 그 자식들에 대해 탐색
            if(!visit[adj[x][i]]){ // 방문 하지 않은 노드일때만
                q.push(adj[x][i]); // 큐에 넣고
                visit[adj[x][i]]=true; // 방문처리
            }
        }
    }
}
int main(){
    int u, v;
    scanf("%d%d", &n, &m);
    for(int i=0;i<m;i++){
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int cnt=0;
    for(int i=1;i<=n;i++){
        if(!visit[i]){ // 방문하지 않은 노드일 때만 cnt++
            bfs(i);
            cnt++;
        }
    }
    printf("%d\n", cnt);
}

동일한 코드를 단순히 bfs로 바꾼 것밖에 없다!