[백준/파이썬] 9466번 텀 프로젝트

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

9466번: 텀 프로젝트

dfs문제이다.

하나씩 다 찾아보면 10만 x 10만으로 시간초과가 발생하므로, 필요없는 경우엔 탐색하지 않아야한다.

 

우선 인덱스를 활용하기 위해 약간의 조작을 해주고, 방문하지 않은 인덱스에 대해서 dfs 탐색을 진행한다.

dfs 탐색을 계속 하다가 이미 방문한 곳을 재방문 했다면 사이클에 속해있는지 판단 후, 만약 속해있다면 해당 부분만 정답에 추가해준다!

5 -> 1 -> 4 -> 3 -> 2 -> 1 -> 4 -> 3 ->2 ... 과 같은 경로가 존재할 수 있기 때문!

 

아 그리고 pypy3와 python3는 차이가 좀 있으므로 유의하자..!

개인적으로는 c++는 메모리 초과 문제가 드문데(관리도 파이썬보단 쉽고), 파이썬에서는 왕왕 발생하는 것 같다. 웬만하면 공간 복잡도보단 시간 복잡도를 사람들이 더 많이 신경 쓰고, 더 공부하므로 우선 python3로 제출해보고 시간초과가 뜬다면 pypy3로도 제출해보자. 둘 다 시간초과라면 당연히 문제일테니까!

 

python3와 pypy3 차이!!

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def dfs(x,result):
    visited[x] = True
    cycle.append(x) #사이클을 이루는 팀을 확인하기 위함
    number = arr[x]
    
    if visited[number]: #방문가능한 곳이 끝났는지
        if number in cycle: #사이클 가능 여부
            result += cycle[cycle.index(number):] #사이클 되는 구간 부터만 팀을 이룸
        return
    else:
        dfs(number,result)

for _ in range(int(input())):
    n =  int(input())
    arr = [0] + list(map(int,input().split()))
    visited=[False for _ in range(n+1)]
    result = []
    
    for i in range(1,n+1):
        if not visited[i]: #방문 안한 곳이라면
            cycle = []
            dfs(i,result) #DFS 함수 돌림
    
    print(n - len(result)) #팀에 없는 사람 수