BaekJoon 11724: 연결 요소의 개수[C++] [silver2]

문제 링크

https://www.acmicpc.net/problem/11724

 

문제 설명

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

 

출력

첫째 줄에 연결 요소의 개수를 출력한다.

 

예제 입력 1

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1

2

 

소스코드

#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#define MAX 51
using namespace std;
vector<int> map[1001];
bool check[1001];

void BFS(int start) {
    check[start] = true;
    queue<int> q;
    q.push(start);

    //q에 들어가있다면,
    //모든 간선을 확인한다.
    while (!q.empty()) {
        int now = q.front();
        //queue에 들어가 있는 것을 빼주고
        q.pop();
        

        // 현재 간선과 연결되어 있는 간선을 확인한다.
        for (int i = 0; i < map[now].size(); i++) {
            //만약에 방문하지 않은 곳이라면
            if (check[map[now][i]] == false) {
                //true로 바꾸어주고
                check[map[now][i]] = true;
                //다음 방문으로 체크해준다.
                q.push(map[now][i]);
            }
        }

    }
}

int main()
{
    int N, M;
    int num1, num2;
    int cnt = 0;
    cin >> N >> M;
    // N 정점의 개수
    // M 간선의 개수
    for (int i = 0; i < M; i++) {
        cin >> num1;
        cin >> num2;
        //간선 연결해주기
        map[num1].push_back(num2);
        map[num2].push_back(num1);
    }

    sort(map->begin(), map->end());

    for (int i = 1; i <= N; i++) {
        if (check[i] == false) {
            cnt++;
            BFS(i);
        }
            
    }
    cout << cnt << endl;
}

 

 

 

리뷰

이번 일주일은 DFS, BFS 공부에 몰두!