[ 백준 13023 ] ABCDE (C++)

백준의 ABCDE(13023) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제는 친구 관계가 성립하는 5명이 있으면, 1을 그게 안된다면 0을 출력하는 문제이다.

   DFS를 통해서 쉽게 구현할 수 있다. 본인은 친구관계를 표시해주기 위해서 Vector를 사용했으며

   a와 b가친구라면 V[a].push_back(b), V[b].push_back(a)를 해줌으로써 양방향으로 모두 친구관계를 성립하도록

   입력을 저장해 주었다.

2) DFS의 구현방법은 어렵지 않다. 모든 정점(모든 사람의 번호)에서 시작을 하면서, 아직 탐색하지 않은 친구관계인 사람을

   찾아가면서, DFS를 계속해서 호출해준다. DFS의 종료는 총 사람이 5명이 되면 종료를 시키면 된다.

  

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<vector>
 
#define endl "\n"
#define MAX 2000
using namespace std;
 
int N, M;
bool Visit[MAX], Answer;
vector<int> V[MAX];
 
 
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 Idx, int Cnt)
{
    if (Cnt == 5)
    {
        Answer = true;
        return;
    }
    Visit[Idx] = true;
    
    for (int i = 0; i < V[Idx].size(); i++)
    {
        int Next = V[Idx][i];
        if (Visit[Next] == true) continue;
        DFS(Next, Cnt + 1);
        if (Answer == true) return;
    }
    Visit[Idx] = false;
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        memset(Visit, false, sizeof(Visit));
        DFS(i, 1);
        if (Answer == true) break;
    }
 
    if (Answer == true) cout << 1 << endl;
    else cout << 0 << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}