[C++] 백준 온라인 저지 11724번 연결 요소의 개수 풀이

방향이 없는 연결 그래프에서 서로서로 연결된 덩어리가 몇 개인지 구하는 문제

 

---

문제의 조건

 

1. 첫째 줄에 N개의 정점을 가진 양방향 연결 그래프와 M개의 간선이 주어진다. 

 

2. 둘째 줄부터 간선의 양 끝점이 주어진다. 

 

3. 서로 연결된 요소가 몇 개인지 출력 

 

---

풀이 과정

 

앞전에 풀었던 컴퓨터 바이러스 문제처럼 몇 개의 정점이 간선을 통해 서로 연결되어 있는지 확인하면 될 거라고 생각했습니다. 

연결 요소라는 말이 헷갈렸는데 질문 게시판 보니까 컴퓨터 바이러스 문제처럼 간선으로 서로서로 연결된 것들을 한 덩어리로 치는 것이 맞더라고요. 

 

풀이

1. 양방향 그래프를 만든 뒤 BFS로 현재 정점에서 방문할 수 있는 곳들을 모두 방문한다. 

 

2. 1번 과정이 끝나고 나면 한 연결 요소(덩어리) 탐색이 끝난 것이기 때문에 정답 갯수 하나 증가 

 

3. 모든 정점을 방문할 때까지 위 과정을 반복한다. 

 

---

 

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

using namespace std;

int main(int argc, const char * argv[])
{
    int N, M;
    cin >> N >> M;
    
    //양방향 그래프 세팅 
    vector<vector<int>> graph(N + 1);
    for (int i = 0; M > i; i++)
    {
        int from, to;
        cin >> from >> to;
        graph[from].emplace_back(to);
        graph[to].emplace_back(from);
    }
    
    vector<bool> visited(N+1, false);
    
    int answer = 0;
    
    //모든 정점을 방문할 때까지 반복 
    for (int i = 1; visited.size() > i; i++)
    {
        //현재 정점을 방문하지 않았으면 현재 정점에서 연결된 모든 정점을 방문한다. 
        if (!visited[i])
        {
            queue<int> q;
            q.emplace(i);
            
            visited[i] = true;
            
            while (!q.empty())
            {
                auto curVertex = q.front();
                q.pop();
                
                for (int j = 0; graph[curVertex].size() > j; j++)
                {
                    auto neighbor = graph[curVertex][j];
                    if (!visited[neighbor])
                    {
                        q.emplace(neighbor);
                        visited[neighbor] = true;
                    }
                }
            }
            answer++; //가능한 모든 정점 방문이 끝나면 한 연결 요소(덩어리) 탐색이 끝난 것 
        }
    }
    
    cout << answer;
    
    return 0;
}