[BOJ / C++] #11724 연결요소의 개수

🍎 문제 링크

문제 풀이

1. 입력을 연결리스트로 받는다.
2. bool visited 배열을 활용하여 BFS, DFS 두 방법 으로 해결 할 수 있다.
   • 노드를 순차적으로 탐색하면서 아직 방문된 적 없는 경우 bfs나 dfs를 호출 한 후 cnt++

입력, main

int main(){
    cin>>N>>M;

    for(int i=0;i<M;i++){
        int s,e;
        cin>>s>>e;
        map[s].push_back(e);
        map[e].push_back(s);
    }

    int cnt=0;

    for(int i=1;i<=N;i++){
        if(!visited[i]){
            bfs(i);
            //dfs(i);
            cnt++;
        }
    }
    cout<<cnt<<"\n";

}

BFS

void bfs(int start){
    queue<int> q;

    visited[start]=true;
    q.push(start);

    while(!q.empty()){
        int cur=q.front();
        q.pop();

        for(int i=0;i<map[cur].size();i++){
            if(!visited[map[cur][i]]){
                visited[map[cur][i]]=true;
                q.push(map[cur][i]);
            }
        }
    }
}

DFS

void dfs(int start){
    visited[start]=true;

    for(int i=0;i<map[start].size();i++){
        if(!visited[map[start][i]]){
            visited[map[start][i]]=true;
            dfs(map[start][i]);
        }
    }

}

전체 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define MAX 1000+1
vector<int> map[MAX];
bool visited[MAX];
int N,M;

void bfs(int start){
    queue<int> q;

    visited[start]=true;
    q.push(start);

    while(!q.empty()){
        int cur=q.front();
        q.pop();

        for(int i=0;i<map[cur].size();i++){
            if(!visited[map[cur][i]]){
                visited[map[cur][i]]=true;
                q.push(map[cur][i]);
            }
        }
    }
}

void dfs(int start){
    visited[start]=true;

    for(int i=0;i<map[start].size();i++){
        if(!visited[map[start][i]]){
            visited[map[start][i]]=true;
            dfs(map[start][i]);
        }
    }

}



int main(){
    cin>>N>>M;

    for(int i=0;i<M;i++){
        int s,e;
        cin>>s>>e;
        map[s].push_back(e);
        map[e].push_back(s);
    }

    int cnt=0;

    for(int i=1;i<=N;i++){
        if(!visited[i]){
            bfs(i);
            //dfs(i);
            cnt++;
        }
    }
    cout<<cnt<<"\n";

}