2331번 반복수열(DFS, 싸이클)

#문제링크 : https://www.acmicpc.net/problem/2331

전략 : 문제에서 주어진 수 중에 나올 수 있는 가장 큰 수를 어림잡아 보면, A : 9999, P : 5 일때, 수열의 다음 수가 40만 보다 작다. 마찬가지로 세번째 수의 최대값은 40만의 자릿수가 6개이기 때문에, 999999로 상정하더라도 (10^5 x 6) = 60만보다 작다. 즉, 주어진 수열의 최대값은 100만을 넘지 않는다. 이를 이용해서 check배열을 최대 100만까지 만들어준다. 수열의 다음값이 어떤 수가 올지는 모르지만, 100만을 넘지 않기 때문에 배열을 100만까지 선언해놓는다. 수열이 진행됨에 따라 어느순간부터 싸이클을 돌기 시작한다. 싸이클을 돌기 시작하는 순간은 첫 중복수가 등장하는 순간이다. DFS로 재귀를 진행하면서 다음 숫자를 방문하고 방문한 숫자는 방문했다는 체크표시를 해두면서 벡터에 숫자들을 담는다. 만약, 수열을 만들어 나가다가 이미 방문 되어있는 숫자를 다시 방문하는 순간이 오면, 그 때의 값(point)을 따로 저장하고 재귀를 나온다. 벡터에 담겨있는 숫자들 중 point값과 같은 값을 찾아 해당 인덱스를 출력하면 그 값이 싸이클에 포함되지 않는 수의 갯수가 된다. 벡터의 인덱스는 0부터 시작하므로, 자연스럽게 point값이 등장한 순서보다 하나 작은 순서가 출력된다.

1. Code

※주의사항

1. check배열을 다양한 용도로 활용할 수 있다. (check배열에 순서를 저장하면 벡터를 쓰지 않아도 된다.)

2. Code