[백준] C++ 11724번 연결 요소의 개수 실버2 - 그래프

문제 : https://www.acmicpc.net/problem/11724
분류 : 그래프, 깊이, 너비 우선 탐색(DFS, BFS)

접근

1. 방향이 없는 그래프는 BFS로 풀면 된다.
2. 방향이 없기 때문에 점들이 선으로 연결되어 있다고 표시해주면 된다.
3. 예제를 그려보면 다음과 같다. 때문에 답이 2이다.
4. 정점들을 방문하여 연결되어 있는 선을 확인하면 된다.
   4.1 1을 체크하여 방문한적이 없으면 1에 연결되어 있는 2를 방문
   4.2 2에 연결되어 있는 5를 방문
   4.3 5에 연결되어 있는 1은 처음에 방문을 했기 때문에 순회 종료. 이런식으로 하다보면 된다.
   

슈도코드

// 방향이 없기 때문에
for M
[a][b] = 1
[b][a] = 1

// 점을 방문한 적 없으면 순회
visited[i] x 
  bfs(i)
  끝나면 cnt++
  
bfs()
  q에 처음값 삽입
  
  for 정점
    연결되어 있는 점 방문한적 없으면 
      방문했다 표시

풀이

#include <iostream>
#include <queue>
#define MAX 1001
using namespace std;

int N, M;
int graph[MAX][MAX];
bool visited[MAX] = {false, };

void BFS(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        
        for(int i = 1; i <= N; i++) {
            if (graph[v][i] == 1 && !visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int a, b, connected = 0;
    cin >> N >> M; // 정점 수, 간선 수
    
    for(int i = 0; i < M; i++) {
        cin >> a >> b;
        graph[a][b] = 1; // 연결 처리
        graph[b][a] = 1;
    }
    
    for(int i = 1; i<= N; i++) { // N이 1이상인 조건이 있기 때문에
        if (!visited[i]) {
            BFS(i);
            connected++;
        }
    }
    cout << connected;
    return 0;
}