[Python] 백준 #9466 텀 프로젝트

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

 

[코드]

import sys

N=int(sys.stdin.readline().rstrip())

for i in range(N):
    n=int(input())
    List=[0]+list(map(int,sys.stdin.readline().rstrip().split()))
    visited=[0]*(n+1)
    
    group=1
    
    for j in range(1,n+1):
        if visited[j]==0:
            while visited[j]==0:
                visited[j]=group
                j=List[j]
            while visited[j]==group: #거꾸로 돌아가면서 같은 그룹애들이면 -1로 체크
                visited[j]=-1
                j=List[j]
            group+=1
    cnt=0        
    for i in visited:
        if i!=0 and i!=-1:
            cnt+=1
    print(cnt)
    

[시간/메모리]

46172KB / 4204 ms

 

[etc]

추가로.. c언어로 알고리즘을 배울 때, 사이클을 찾기위해 union find 를 배운적이 있다.

재귀함수를 이용해서 구하는건데.. 파이썬에서는 왜인지모르게 효율적이지 못하게 느껴진다