[ SWEA 5521 ] 상원이의 생일파티 (C++)

SWExpertAcademy의 상원이의 생일파티(5521 / D5) 문제이다.

[ 문제풀이 ]

친한 친구의 친한 친구까지 초대장을 줄 때 총 몇명의 친구에게 주어야 하는지 구해야 하는 문제이다.

본인은 이 문제를 너비우선탐색(BFS)로 풀어보았다.

BFS 탐색을 진행할 때, Depth가 2이하일 때 까지만 탐색하고, 그 이상일 경우에는 탐색을 하지 않고 넘어가도록

구현했다.

왜냐하면, 친한 친구의 친한 친구까지만 초대장을 주기 때문에, 친한친구 = Depth 1 , 친한친구의 친한친구 = Depth2 이므로

Depth가 2인 경우에 더 탐색을 해버리면, 친한 친구의 친한친구의 친한친구까지 초대를 해버리기 때문에, Depth가 2인

정점에서는 탐색을 하지 않도록 구현해 주었다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 510
using namespace std;
 
int N, M, Answer;
bool Visit[MAX];
vector<int> Friend[MAX];
 
void Initialize()
{
    Answer = 0;
    memset(Visit, false, sizeof(Visit));
    for (int i = 0; i < MAX; i++) Friend[i].clear();
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b; cin >> a >> b;
        Friend[a].push_back(b);
        Friend[b].push_back(a);
    }
}
 
void Solution()
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(1, 0));
    Visit[1] = true;
 
    while (Q.empty() == 0)
    {
        int Cur = Q.front().first;
        int Depth = Q.front().second;
        Q.pop();
 
        if (Depth == 2) continue;
        
        for (int i = 0; i < Friend[Cur].size(); i++)
        {
            int Next = Friend[Cur][i];
            if (Visit[Next] == false)
            {
                Visit[Next] = true;
                Answer++;
                Q.push(make_pair(Next, Depth + 1));
            }
        }
    }
}
 
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;
 
}