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

#include <iostream>
#include <queue> // bfs
using namespace std;

int N, M, cnt = 0;
int map[1001][1001] = {0}; // 그래프
bool visited[1001] = {false}; // 방문 체크
queue<int> q; // 큐

void BFS(int n){
    if(!visited[n]){
        visited[n] = true; // 방문체크
    }
    q.push(n); // 큐에 노드 넣기

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

        for(int i = 1; i <= N; i++){
            if(map[node][i] == 1 && !visited[i]){ // 노드에 연결된 노드가 있고 방문되지 않았다면
                visited[i] = true; // 방문체크
                q.push(i); // 연결 노드 큐에 넣기
            }
        }
    }
}

int main(int argc, char **argv){
    scanf("%d %d",&N,&M);

    int a, b;
    for(int i=1; i<=M; i++){
        scanf("%d %d",&a,&b);
        map[a][b] = 1;
        map[b][a] = 1; // 간선 연결, 방향이 없으니까 a -> b, b -> a
    }

    for(int i=1; i<=N; i++){
        if(!visited[i]){
            BFS(i);
            cnt++; // 방문하지 않았다면 카운터 세기
        }
    }

    printf("%d", cnt);

    return 0;
}

bfs 연습용으로 푼 문제.

bfs로 노드를 하나하나씩 체크해준다. 한 번 bfs를 돌렸을때 방문되지 않은 노드가 있으면 그것이 바로 연결 요소가 아닌 것이 있음을 뜻한다. 따라서 cnt 개수를 올려주고, 그 노드에서 다시 bfs를 돌린다.

아직도 그래프가 너무 어렵다. 그래도 제대로 풀어보기로 노력하고 있으니까 한 달 뒤에는 나아지겠지 화이팅