알고리즘 PS

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

on_doing 2021. 1. 16. 20:59
728x90

www.acmicpc.net/problem/9466

 

9466번: 텀 프로젝트

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을

www.acmicpc.net

 

[코드]

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 를 배운적이 있다.

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

728x90
댓글수0