[c++][백준 13023][DFS] ABCDE - 컴도리돌이

---

13023번: ABCDE

---

풀이 과정

-  모든 노드들은 ABCDE 친구 관계가 성립하는지 그래프 탐색을 한다.

- 방문한적이 없는 노드는 해당 DFS로 탐색하고 깊이를 1 증가 시킨다. 깊이가 총 5번이면 관계가 성립 되었기에 ans 값을 true로 설정하고 return 해준다.

- dfs로 탐색이 끝났는데 ans 값이 false 면 해당 탐색했던 노드는 다시 방문 표시를 false로 설정한다.

#include <iostream>
#include <map>
#include <vector>

using namespace std;

int n,m;
map<int,vector<int>> friends;
vector<bool> visited;
bool ans = false;
void dfs(int cur,int depth)
{
    if(depth == 5)
    {
        ans = true;
        return;
    }
    visited[cur] = true;

    for(int i =0; i < friends[cur].size(); i++)
    {
        int next = friends[cur][i];
        if(!visited[next]) dfs(next,depth + 1);
        if(ans) return;
    }
    visited[cur] = false;
}
void input()
{
    cin >> n >> m;
    int a,b;
    visited.resize(n,false);
    for(int i=0; i<m; i++)
    {
        cin >> a >> b;
        friends[a].push_back(b);
        friends[b].push_back(a);
    }
}
void solution()
{
    input();
    for(int i=0; i<n; i++)
    {
        dfs(i,1);
        if(ans)
        {
            cout << ans;
            return;
        }
        else
        {
            visited.clear();
            visited.resize(n,false);
        }
    }
    cout << ans;
}

int main(void)
{
    solution();
    return 0;
}