[BOJ] 텀 프로젝트 (9466, G3)

DFS로 풀 수 있는 문제. 좀 까다로운 문제이다.

문제의 핵심은 "사이클"을 찾아 내는 것이다. 하나의 원소를 넣고, 돌면서 방문 여부를 체크하게 된다. 이 때, 이동한 경로를 넣고, 이미 방문했는데, 사이클 리스트에 있다면 사이클이라고 판단, 반환하는 것이다.

문제는, 사이클에서 일부 삐져나온 상황이다. (2 4 7 3 4 7 3.... 이렇게 도는 상황) 이를 주의해서 구현한다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(cur_std, cur_result):
    visited[cur_std] = True
    cur_cycle.append(cur_std)
    next_std = std_list[cur_std]
    
    if visited[next_std]:
        if next_std in cur_cycle:
            # 사이클이 돌고 있다. 다음 학생의 위치를 찾아 리스트를 자른다.
            cur_result += cur_cycle[cur_cycle.index(next_std):]
    else:
        dfs(next_std, cur_result)        
          
t = int(input())
for _ in range(t):
    answer = 0
    std = int(input())
    std_list = [0] + list(map(int, input().split()))
    visited = [False] * (std + 1)
    cur_result = []
    for i in range(1, std+1):
        if not visited[i]:
            cur_cycle = []
            dfs(i, cur_result)        
    print(std - len(cur_result))