9466번/DFS 텀 프로젝트/파이썬

📕 문제

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

 

📗실행결과

 

 

📄 내가 생각한 풀이

 

 

사이클이 만들어지는 학생이 팀이 만들어짐.

 

 

💻 답안

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)



# 테스트케이스인 int(input())만큼 수행 
for _ in range(int(input())):
    # n : 학생 수
    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행렬 생성해서
            cycle = []
            # dfs함수 돌림
            dfs(i,result)

    # 팀에 없는 사람수
    print(n-len(result))

 

☺️ 느낀점

DFS/BFS 어려움

참고자료 봐야 구현가능

 

 

😉 참고

https://oh2279.tistory.com/138

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

 

 

https://www.youtube.com/watch?v=yPuow6aACvE