[ SWEA 7465 ] 창용 마을 무리의 갯수 (C++)

SWExpertAcademy의 창용 마을 무리의 갯수(7465 / D4) 문제이다.

[ 문제풀이 ]

1) 사람과 사람간의 관계를 가지고 총 몇개의 무리가 존재하는지 알아내야 하는 문제이다.

   여기서 '무리' 라는 것은 알고 있는 사람의 알고있는 사람, 즉 몇 단계 거쳐서 알 수 있는 관계더라도 하나의 무리라고

   판단한다.

   본인은 깊이우선탐색(DFS)를 이용해서 접근해 보았다. 시작점 x번 사람으로부터 몇 단계 거쳐 알 수 있는 사람들까지

   모두 탐색하면서, 이미 탐색한 사람들을 Visit배열로 체크해 주었다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define MAX 1000 + 1
using namespace std;
 
int N, M, Answer;
vector<int> V[MAX];
bool Visit[MAX];
 
void Initialize()
{
    Answer = 0;
    memset(Visit, false, sizeof(Visit));
    for (int i = 0; i < MAX; i++) V[i].clear();
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b; cin >> a >> b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
}
 
void DFS(int x)
{
    Visit[x] = true;
    for (int i = 0; i < V[x].size(); i++)
    {
        int nx = V[x][i];
        if (Visit[nx] == false)
        {
            DFS(nx);
        }
    }
}
 
void Solution()
{
    if (M == 0)
    {
        Answer = N;
        return;
    }
 
    for (int i = 1; i <= N; i++)
    {
        if (Visit[i] == false)
        {
            DFS(i);
            Answer++;
        }
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}