어떻게 풀까?

: 백트래킹

첫번째 풀이

: dfs로 접근하면 되지 않을까? 생각함.
그리고 visied의 상태값을 통해 출력하면 된다고 생각했으나.

• 예제 4번을 처리하기 위해서 각 정점을 서로 엮어놓았기 때문에 절대로 dfs로는 해당 문제를 풀수 없었다.

• 문제에서도 단방향이라는 설명은 없다. 연결되면 a와 b는 친구 관계라는 내용이 있다. 그래서 두개를 서로 엮어야 한다.

• 이렇게 구성함.
  

• dfs로 풀수 없다고 생각했냐면 입력 예제 1번을 보면,
  : 지금 이상태로 하게 되면, 예제 3번의 visited도 전부다 true 처리된다.

다시 생각해보기

• 반드시 벡터는 이렇게 만들어야 한다!
  

• 0번 정점부터 연결된 정점을 방문해보자.
  0->1->2->3->0 끝? 1,4 는 어떻게 할 건데???
  처리하려면 dfs 에서 continue 해서
  백트래킹해서 0->1->4 로 가야 한다.
  

• 그런데 지금 이런식으로 하면 3번 예제 이것도 1이 나와야 한다.
  왜냐하면 0->1 완료 복귀 0->2 완료 복귀 0->3 완료 복귀 0->4 완료 복귀
  0-> 5 완료 복귀 끝!
  

• 다시 예제 2로 돌아와서 4,1부터 시작해보면?
  4->1->0->3->2->1 이런식으로 탐색이 가능하다.

• 즉! dfs 진행할때 복귀하지 않고 한번에 다이렉트로 모든 정점을 방문할 수 있을까???? 라는 생각을 해야 한다. 이게 된다면 1이고, 아니면 0이다.
  왜냐하면

1) 3번의 경우는 한번에 0번에서 5까지 도달할 수 없지만.

2) 2번의 경우는 가능하다. : 위의 4번 정점부터 진행.

결론

위의 2개를 확인해보면서 재귀를 하면서 카운팅 갯수를 판단하면 되지 않을까? 란 생각을 해야 한다. 문제에서 문제의 조건에 맞는 친구들 5명! 이라는 것을 생각해내야 한다.
백트래킹해서 5명만 만들기만 하면 종료되겠구나 라는 것을 생각해야 한다.