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

🔗알고리즘 문제

그래프 탐색 문제를 약간 응용하여 해결한 문제. 아직 문제를 해결할 수 있다 정도이고 시간과 메모리는 챙기지 못한 것 같아 아쉽다..

문제 분석

이 문제는 그래프의 정보가 주어졌을 때 그래프가 몇 덩이로 나뉘어져 있는지 알아내는 문제이다.

발상

그래프가 몇 덩이인지 알아내기 위해서 그래프 탐색이 한번 진행될 때 시작점에서 연결 된 모든 노드를 방문하고 돌아온다는 사실을 응용하였다.

즉, 그래프 탐색이 실행되는 횟수 = 그래프가 조각난 갯수라는 말이 된다.

알고리즘 설계

1. 그래프의 정보를 입력받는다.
2. 1번부터 마지막 노드까지 for문을 진행하며 아직 방문하지 않은 노드가 있을 시 그래프 탐색을 진행한다.
3. 그래프 탐색을 진행할 때마다 answer를 1씩 증가시킨다.

코드

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

void bfs(vector<int> *graph, int start, bool *check){
    queue<int> q;

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

    while(q.empty() == false){
        int node = q.front();
        q.pop();

        for(int i = 0; i < graph[node].size(); i++){
            int next = graph[node][i];

            if(check[next] == true)
                continue;

            check[next] = true;
            q.push(next);
        }
    }
}

int main(){
    vector<int> graph[1001] = {};
    bool check[1001] = {};
    
    int n;
    int m;

    int answer = 0;

    cin >> n >> m;

    for(int i = 0; i < m; i++){
        int cur;
        int next;
        cin >> cur >> next;
        graph[cur].push_back(next);
        graph[next].push_back(cur);
    }

    for(int i = 1; i <= n; i++){
        if(check[i] == true)
            continue;
        
        bfs(graph, i, check);
        ++answer;
    }

    cout << answer;
}