딱 보자 마자 DFS,BFS 문제구나 생각이 들긴 했는데 아직 잘 모르겠어서 못 풀었다.
차근 차근 풀이를 살펴보겠다.
sys.setrecursionlimit(10**7)
최대 재귀를 늘려줘야 런타임 에러를 피할수 있다고 한다.
DFS는 재귀또는 스택을 이용해서 푸는 문제가 많다.
dfs함수를 정의해서 dfs함수가 들어가면 방문했다는 거니깐 visited 리스트에 값을 1로 바꿔준다. 그리고 그 다음 값을 넣어줘야하므로 next를 선언해주었다. 그리고 다음 값에 방문을 안한거라면(visited[next]==0)이라면 다시 그 함수를 적용한다. 만약 방문을 했다면 함수가 끝나서 나오게 된다. 그렇다면 원래 for문에서 ans가 하나 증가하게 되어서 순환개수가 하나 증가하게 되는 것이다.
data = [0]+list(map(int,input().split()))
왜 이렇게 써야하지?
->그냥 인덱스 1부터 써주려고 하는거였다
import sys
sys.setrecursionlimit(10**7)
T= int(input())
def dfs(v):
visited[v]=1
next= data[v]
if visited[next]==0:
dfs(next)
for _ in range(T):
N= int(input())
data = [0]+list(map(int,input().split()))
visited= [0]*(N+1)
ans=0
for i in range(1,N+1):
if visited[i]==0:
dfs(i)
ans+=1
print(ans)