[BOJ]2668번: 숫자고르기

 

문제: https://www.acmicpc.net/problem/2668

---

유형 태그가 다양한 걸 보니 푸는 방법은 다양한 것 같습니다만,

싸이클 찾기 문제로 해결했습니다.

 

N = 100이니 직접 하나씩 뽑아보면서 탐색하면 터지는 건 자명합니다.

 

문제 예제를 보면 표에서 첫번째 줄에 5번 칸이  -> 5로 가는 걸 볼 수 있습니다.

이걸 보고 자기 자신의 숫자를 가지는 애들이 정답 갯수에 포함된다면,

정답으로 뽑히는 애들은 싸이클 성질을 가지고 있다는 걸 알았습니다.

 

즉, 이 문제는 가장 큰 싸이클을 구하는 문제입니다.

싸이클을 찾는 방법은 위상정렬을 통해 해결하였습니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ2668.cc