[ 백준 11724 ] 연결 요소의 갯수 (C++)

백준의 연결요소의 갯수(11724) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 입력으로 정점의 갯수와 간선의 갯수가 주어지고, 총 몇개의 연결된 형태의 그림이 생겨나는지(?) 구하는 문제이다.

[ 문제풀이 ]

1) 입력으로 간선의 갯수만큼 반복문을 돌면서, 서로 연결된 정점들을 입력받는다.

2) 본인은 MAP 2차원 배열을 이용해서 이 정보를 저장했으며, MAP을 (0,0)부터 사용했기 때문에 입력받는 두 정점들 값에서

   1을 뺀 값을 MAP에 저장했다.

   - 저장할 때, 방향 없는 그래프라고 했으므로 MAP[a][b] = MAP[b][a] = 1로 저장해주었다. (1은 연결됨을 의미)

3) 이런 정점들을 관리하는 문제는 BFS보다는 DFS가 훨씬 편하다. 모든 정점에 대해서 DFS를 실행시키는데, 한 번도

    방문하지 않은 정점에 대해서만 DFS를 실행시켜 주면 된다.

4) 3)의 내용을 좀 더 구체적으로 설명해보면 문제에서 주어진 예제 입력 1번을 예시로 들면

   0과 1 / 1과 4 / 4와 0 / 2와 3 / 3과 5 이렇게 총 5개의 정점이 연결되어 있고, 0번부터 시작한다. 0번의 경우 1번과

   연결되어 있으므로, 1번으로 가게되고, 1번은 4번으로 가게된다. 4번에서는 다시 0번으로 오게되는데, 이미 0번은

   처음에 방문했던 곳이기 때문에, 지나쳐버리고 더 이상 연결된 점이 없기 때문에 그대로 종료.되고, 이렇게 종료되면

   위의 문제설명에서 말한 연결된 형태의 그림이 1개가 된 것이다.

   그렇게 되면 현재 0번, 1번, 4번 점이 이미 방문한 점이 되어버렸고, 그 다음 정점은 1번부터 시작하는 것이 아닌

   2번부터 시작할 것이다. 즉, DFS가 재귀를 통해서 계속해서 연결된 정점을 호출하지만, 전체적인 DFS로 봤을 때는

   결과적으로 DFS가 실행된 횟수가 연결요소의 갯수가 되는 것이다.

[ 소스코드 ]

 

#include<iostream>
 
#define endl "\n"
#define MAX 1000
using namespace std;
 
int N, M, Answer;
int MAP[MAX][MAX];
bool Visit[MAX];
 
void Input()
{
    Answer = 0;
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        a = a - 1;
        b = b - 1;
        MAP[a][b] = 1;
        MAP[b][a] = 1;
    }
}
 
void DFS(int Point)
{
    Visit[Point] = true;
    for (int i = 0; i < N; i++)
    {
        if (MAP[Point][i] == 1 && Visit[i] == false)
        {
            DFS(i);
        }
    }
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        if (Visit[i] == false)
        {
            Answer++;
            DFS(i);
        }
    }
}
 
void Solve()
{
    Input();
    Solution();
 
    cout << Answer << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}