#2668 숫자 고르기

알고리즘 핵심은 1부터 n까지 사이클을 형성하는 노드를 찾아가면서 싸이클을 형성하는 노드 갯수만큼 카운트값을 올리고 방문처리가 돼 있는 노드는 스킵하여 출력하는 것이다.

 

알고리즘 순서

1.  1부터 n까지 반복문 형성 후 다시 1부터 n까지 사이클을 형성하는 노드들을 방문처리해준다.

2. dfs를 통해 처음 입력한 노드가 재귀를 통해 다시 나오게 된다면 true를 리턴하고 재귀를 해준 dfs함수가 역순으로 되돌아가면서 사이클 크기만큼 cnt값을 올려주며 true를 반환한다.

3. 사이클을 형성하지 않을시 언젠가 방문이 돼 있는 노드를 방문하게 되면서 false를 리턴하고 true가 있는 조건문에는 들어갈 수 없게 된다. 그래서 cnt값은 변화가 없고 false를 반환하게 된다. 

4. dfs 안에서 2,3 과정을 고려하면서 main에서 n 노드까지 방문이 끝난 후 cnt값과 사이클을 형성하는 노드를 순서대로 출력한다.

 

소스코드