[백준] 9466번 텀 프로젝트 (Python)

백준 9466 텀 프로젝트

구글링해서 본 답과 내가 적은 코드가 조금 다르다. 일반적으로 Cycle detection은 DFS 탐색을 하여 방문했던 노드를 또 방문하게 되면 Cycle을 가진 것으로 판단한다. 나는 BFS 탐색을 했고, set과 defaultdict 자료 구조를 활용했다.

1. 후보 set을 만들고 방문할 때마다 set에서 제거한다.
2. 사이클을 구성하는 노드의 개수를 얻기 위해 defaultdict 자료구조를 활용한다.
3. defaultdict에 몇 번째 방문한 노드인지 카운트하고 이미 방문했는데 defaultdict에 0이 아닌 값이 있다면, 방문한 적이 있다는 뜻이므로 카운트 한 값에서 dict에 저장된 값을 빼 몇 개의 노드가 사이클을 구성하는지 구한다.
4. 이미 방문했지만, defaultdict에 0이 저장되어 있다면, 이번 탐색에서는 해당 노드를 방문한 적이 없기 때문에, 이미 탐색을 한 부분을 피하기 위해서 반복문을 종료한다.

import sys
from collections import defaultdict

input = sys.stdin.readline

for _ in range(int(input().strip())):
    n = int(input().strip())
    p = [0] + list(map(int, input().split()))
    candidates = set(range(1, n + 1))
    res = n
    while candidates:
        c = candidates.pop()
        cnt = 1
        d = defaultdict(int)
        while True:
            d[c] = cnt
            cnt += 1
            if p[c] in candidates:
                candidates.remove(p[c])
                c = p[c]
            else:
                if d[p[c]] != 0:
                    res -= cnt - d[p[c]]
                break
    print(res)