백준(BOJ) 9466 텀 프로젝트(Python)

 

DFS 문제.

팀을 구성하는 사이클을 찾아주면 된다.

DFS를 진행하는 첫 노드를 조상 노드라고 임의로 칭할 때,

이 조상 노드를 끝까지 들고 가면서 탐색을 진행한다.

그러면 탐색이 끝나는 노드의 경우,

​

1. 내가 나를 가리키는 노드
2. 내가 다른 사이클을 가리키는 노드
3. 내가 내 사이클을 가리키는 노드

​

이 세 경우만 존재하게 될 것이다.

그 중 팀을 구성하는 사이클인 경우는 3.하나이므로,

3.인 경우에 한해 노드를 거슬러 올라가며 3.에서 가리킨 마지막 노드가 나올 때까지 개수를 세주면

해당 개수가 하나의 사이클을 이룬 노드들의 개수가 된다.

이 사이클을 모든 노드에 대해 찾아주면 된다.

​

그리고 내가 나를 가리키는 경우만 따로 빼줬다.

​

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
#input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)

cnt=0

def func(x,p):
    global cnt
    if x==L[x]:
        return 0
    elif visited[x]==p:
        cnt+=1
        return L[x]
    if not visited[x]:
        visited[x]=p
        check=func(L[x],p)
        if check:
            cnt+=1
            if check==x:
                return 0
            else:
                return check
        else:
            return check
        
    

for _ in range(int(input())):
    n=int(input())
    L=[0]+list(map(int,input().split()))
    visited=[0]*(n+1)
    result=[]
    for i in range(1,n+1):
        if L[i]!=i and not visited[i]:
            cnt=0
            func(i,i)
            n-=cnt
        elif L[i]==i:
            n-=1
            visited[i]=i
    print(n)

 

PS를 놓고 개발만 하다 오니까

PS가 은근 재밌게 느껴진다.