JArchive 프로그래밍 일기

문제

연결 요소의 개수 백준 11724번

리뷰

연결 요소의 개수를 구하는 문제다.

인접리스트 형식으로 간선 정보를 입력받았다.

DFS, BFS 중에서 BFS를 선택해서 풀었다.

첫 방문이라면 answer 를 1로 만들고 BFS를 시작한다.

만약, 정점을 다르게 해서 check 배열을 확인했을 때 미방문 노드가 있다면, 다른 클러스터의 노드들이 있다는 것이다.

answer 가 1인채로 프로그램이 종료 된다면, 하나로 시작해서 모든 정점을 방문했다는 뜻이니까 모든 노드가 하나의 클러스터 안에 있다는 것이다.

코드

#include <iostream> 
#include <vector>
#include <queue>
#include <cstring> // memset()
#include <algorithm>
using namespace std;

int N, M;
int answer;
vector<int> V[1001];
int check[1001];

void BFS(int idx){

    queue<int> qu;

    check[idx] = 1; // 첫 노드부터, 방문하고 큐에 푸시  
    qu.push(idx);

    while(!qu.empty()){

        int x = qu.front();
        qu.pop();

        int togo_size =  V[x].size(); // x와 인접한 노드 개수 (==방문 확인할 노드)

        for(int i = 0; i < togo_size; i++){
            int next = V[x][i];

            if(!check[next]){ // 미방문이라면, 방문하고 큐에 푸시  
                check[next] = 1; 
                qu.push(next);
            } 
        }
    }

}

int main(void){

    cin >> N >> M; // 노드, 간선 개수  

     int st, end;

     for(int i = 0; i < M; i++){

         cin >> st >> end;    
        V[st].push_back(end);
        V[end].push_back(st);
    } // 입력받기 끝


    // 모든 정점을 시작으로 탐색  
    for(int i = 1; i <= N; i++){

         if(!check[i]){ // 첫 방문이면  
             answer++; 
             BFS(i);
        }
    } 

    cout << answer;

    return 0;    
}