백준 9466 텀 프로젝트 Python 3

https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ9466.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from collections import defaultdict
sys.setrecursionlimit(200001)
input = sys.stdin.readline

def dfs(now):
    global team
    visit[now] = 1
    route.append(now)
    if visit[choice[now]]:
        if choice[now] in route:
            team += route[route.index(choice[now]):]
            return
    else: dfs(choice[now])


T = int(input())
for _ in range(T):
    n = int(input())
    choice = [0] + list(map(int, input().split()))
    team = list()
    visit = [0] * (n + 1)
    for i in range(1, n+1):
        if not visit[i]:
            route = []
            dfs(i)
    print(n-len(team))

---

풀이 과정

import sys
from collections import defaultdict
#재귀 제한 늘리기
sys.setrecursionlimit(200001)
input = sys.stdin.readline

def dfs(now):
    global team
    #방문처리 후 탐색 경로에 현재 학생 번호를 담는다
    visit[now] = 1
    route.append(now)
    
    #현재 학생이 선택한 학생이 이미 선택된 경우,
    if visit[choice[now]]:
    	#탐색 경로에 선택한 학생이 포함된 경우, 사이클을 이루므로 팀이 결성된다
        if choice[now] in route:
        	#사이클을 이룬 학생들을 team에 추가한다
            team += route[route.index(choice[now]):]
            return
            
    #현재 학생이 선택한 학생이 이전에 선택되지 않은 경우, 탐색을 이어나간다
    else: dfs(choice[now])


T = int(input())
for _ in range(T):
    n = int(input())
    
    #학생별 선택을 담는 리스트 choice[i] = i번 학생이 선택한 학생 번호
    choice = [0] + list(map(int, input().split()))
    
    #팀 매칭을 완료한 학생 번호를 담는 리스트
    team = list()
    
    visit = [0] * (n + 1)
    for i in range(1, n+1):
    	#이전에 방문하지 않은 경우, 탐색을 시작한다
        if not visit[i]:
        	#탐색 경로를 담는 리스트
            route = []
            dfs(i)
    
    print(n-len(team))

#시간복잡도 = O(T(V+E)), 공간복잡도 = O(n)