Written by nodejs-style
on 2021-11-25

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

728x90

풀이 과정

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

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

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

#include #include #include using namespace std; int n,m; map> friends; vector 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> a >> b; friends[a].push_back(b); friends[b].push_back(a); } } void solution() { input(); for(int i=0; i

728x90

from http://comdolidol-i.tistory.com/261 by ccl(A) rewrite - 2021-11-25 09:26:36

Top