백준 11724 - 연결요소의 개수 - 그래프 탐색 및 순회

 

시간 제한메모리

3 초

512 MB

 

문제

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

입력

 

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

출력

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

 

---

 

 

1. 문제 해석

* 그래프 연결요소란?

그래프가 이어져 있는 노드끼리 같은 색으로 선을 긋다보면,  여러가지 색깔의 그룹이 생긴다.

그러한 그룹들을 그래프의 연결 요소들이라고 부른다. 

 

쉽게 설명한 블로그 :

https://velog.io/@kjh107704/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8C

 

 

 * 그래프 연결요소를 어떻게 셀 수 있을까? 

일전에 풀어보았던 단지번호 붙이기 문제가 기억났다. 

이 문제도 연결된 집들을 묶어서 한 단지라고 표현해서 단지 수를 나타내는 문제였다.

결국 단지가 연결요소로 치환된 것이지 다른 것이 아무것도 없는 문제였던 것이다!

 

여기까지 생각하고 난 뒤, 해당 문제와 동일한 논리로 코드를 설계하였다.

: BFS로 노드들을 방문하되 각 BFS 마다 visit의 값을 1씩 증가시켜 그 값이 곧 단지수, 여기서는 연결 요소의 수를 나타내도록 하는 것이다. 

 

 

* 제출 하고 한번에 통과하지 못하고 잠시 오류가 났는데, 그 이유는 그래프를 순회할 때 1~N을 순회해야하는데 인덱스를 잘못 접근했던 탓이었다.

 

그래프 문제는 매번 해당 노드 번호와 일치하는 인덱스를 사용하므로, 0에 접근하거나 N-1까지만 접근하는 경우가 없도록 처음부터 염두에 두고 시작하도록 하자!

 

 

2. 구현

구현한 코드는 다음과 같다. 

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

#define MAX 2000000

int N,M;
vector <vector<int> > g(1001);
int visit = 1;
int visited[1001] = {0,};
priority_queue<int> PQ;

void input()
{
    int u, v; // N<=1000
    for(int i=0;i<M;i++)
    {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
}

void BFS(int i)//i 번째 노드 방문후 BFS 순회!
{
    if(visited[i])
        return; //큐에 저장되어있는데 pop되기 전에 방문될 수 있다.
    visited[i] = visit;
    PQ.push(i);

    while (PQ.size()) {
        int next = PQ.top();
        PQ.pop();
        int j = -1;
        while (++j < g[next].size())//adjecent nodes
        {
            if (visited[g[next][j]] == false) {
                PQ.push(g[next][j]);
                visited[g[next][j]] = visit;
            }
        }
    }
    visit++;
    return ;

}

void find_group()
{
    //단지 순회를 하듯이 방문하지 않은 노드들만을 방문하되, 시작점에서 인접노드까지만 이동하도록 한다. (BFS)
    //그래프 내에서 순회를 하면서 BFS를 한 횟수가 곧 연결요소의 개수일 것이다.
    for(int i=1;i<=N;i++)
    {
        if(visited[i] == 0)
            BFS(i);

    }
}

int main()
{
    cin >> N >> M;
    input();
    find_group();
    if(visit == 0)
       cout << visit;
    else
        cout << visit-1;
}