[백준] 9466 - 텀 프로젝트 (Python)

문제 출처 :

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

문제 풀이:

• 이 문제는 처음에 각 학생들마다 방문과 싸이클을 따로 구하려고 하다보니 무척 어려웠다.
• 사실상 이문제는 싸이클을 구하는 문제 인데, 싸이클의 핵심은 node가 root를 가르키면 된다는 점이다.
• 이점을 고안해서 dfs를 사용하면 해결된다.
• 코드에선 방문 하지 않은 경우에는 team을 리스트 변수로 생성하고(이건 추후에 cycle 후보들이 담긴다), 그후 dfs 함수를 호출한다.
  • dfs 함수에선 방문여부를 체크하고 방문 표시를 하며 방문한 번호인데 기존에 있었던 부분이라면 그 부분부터 나머지를 cycle로 간주해서 ans 에 넣어준다.
  • 만약 팀에 없다면 다시 dfs를 써서 재귀로 실행한다.
• 예시를 들자면

5
2 5 4 5 2

에 대해서 생각해보자

 

코드를 실행하면 

arr = [0, 2 , 5 , 4 , 5 ,2 ] 

visited = [1 , 0, 0, 0, 0 ,0]

으로 시작한다.

 

이후 1부터 6까지 for 문안에서 dfs를 실행한다.

i=1인 경우

team=[ ] 

dfs(1) =>

 

visited[1] =1

team = [1]

num = arr[1] = 2

visited[num =2 ] =0 이므로 dfs(2) 실행

 

team=[1]

dfs(2)=>

 

visited[2]=1

team = [1,2]

num = arr[2]=5

visited[5] = 0 이므로 dfs(5) 실행

 

team[1,2]

dfs[5] =>

visited[5]=1

team = [1,2,5]

num = 2

visited[2] =1 (dfs(2)부분) 이므로 if문 실행

num = 2 는 team에 있으므로 ans += team[1 :] (2의 인덱스를 불러오므로)

 

이렇게 보면 cycle이 체크되는걸 알 수 있다.

 

• 풀고나니 간단하지만 푸는 과정에서는 그렇게 간단하지 않았던 문제였다.(아마도 내 실력이 모자라서 그런거겟지만..)
• 또한 사실 in 함수는 list를 전부 돌아야 하기 때문에 visited를 통해 가지치기를 했더라도 시간이 많이 걸릴꺼라고 예상했다. 통과는했지만 굉장히 느린 것을 알 수 있었다.

import sys

sys.setrecursionlimit(1000001)

def dfs(n):
    global ans,visited,arr,team
    visited[n]=1
    team.append(n)
    num = arr[n]

    if(visited[num]):
        if num in team:
            ans += team[team.index(num):]
        return
    else:
        dfs(num)

t= int(input())

for _ in range(t):
    n = int(input())
    arr = [0] + list(map(int,input().split()))
    visited = [1] +[0]*(n)
    ans = list()

    for i in range(1,n+1):
        if(visited[i]==0):
            team = []
            dfs(i)

    print(n-len(ans))